NEERC/garbling/garbling_petr_slow.java

   1 import java.io.BufferedReader;
   2 import java.io.FileReader;
   3 import java.io.PrintWriter;
   4 import java.io.IOException;
   5 import java.util.StringTokenizer;
   6
   7 public class garbling_petr_slow implements Runnable {
   8     class StepDescription {
   9         int[] perm;
  10         long[] numWrites;
  11
  12         StepDescription(int[] perm, long[] numWrites) {
  13             this.perm = perm;
  14             this.numWrites = numWrites;
  15         }
  16     }
  17
  18     private void solve() throws IOException {
  19         int r = nextInt();
  20         int c = nextInt();
  21         long n = nextLong();
  22         String[] map = new String[r - 1];
  23         for (int i = 0; i < r - 1; ++i)
  24             map[i] = nextToken();
  25         StepDescription fullCycle = buildStepDescription(r, c, n, map, (r - 1) * (c - 1));
  26         StepDescription remains = buildStepDescription(r, c, n, map, (int) (n % ((r - 1) * (c - 1))));
  27         StepDescription res = mul(pow(fullCycle, n / ((r - 1) * (c - 1))), remains);
  28         for (int i = 0; i < r * c; ++i)
  29             writer.println(res.numWrites[i]);
  30     }
  31
  32     private StepDescription mul(StepDescription a, StepDescription b) {
  33         int[] perm = new int[a.perm.length];
  34         long[] numWrites = new long[a.perm.length];
  35         for (int i = 0; i < a.perm.length; ++i) {
  36             perm[i] = a.perm[b.perm[i]];
  37             numWrites[i] += a.numWrites[i];
  38             numWrites[a.perm[i]] += b.numWrites[i];
  39         }
  40         return new StepDescription(perm, numWrites);
  41     }
  42
  43     private StepDescription pow(StepDescription a, long k) {
  44         if (k == 0) {
  45             int[] perm = new int[a.perm.length];
  46             for (int i = 0; i < a.perm.length; ++i)
  47                 perm[i] = i;
  48             long[] numWrites = new long[a.perm.length];
  49             return new StepDescription(perm, numWrites);
  50         } else if (k % 2 == 0) {
  51             return pow(mul(a, a), k / 2);
  52         } else {
  53             return mul(pow(a, k - 1), a);
  54         }
  55     }
  56
  57     private StepDescription buildStepDescription(int r, int c, long n, String[] map, int amount) {
  58         int[] sperm = new int[r * c];
  59         for (int i = 0; i < r * c; ++i)
  60             sperm[i] = i;
  61         long[] snumWrites = new long[r * c];
  62         outer: for (int sr = 0; sr < r - 1; ++sr)
  63             for (int sc = 0; sc < c - 1; ++sc) {
  64                 if (amount == 0)
  65                     break outer;
  66                 ++snumWrites[sperm[sr * c + sc]];
  67                 switch (map[sr].charAt(sc)) {
  68                     case 'R': {
  69                         int t = sperm[sr * c + sc];
  70                         sperm[sr * c + sc] = sperm[(sr + 1) * c + sc];
  71                         sperm[(sr + 1) * c + sc] = sperm[(sr + 1) * c + sc + 1];
  72                         sperm[(sr + 1) * c + sc + 1] = sperm[sr * c + sc + 1];
  73                         sperm[sr * c + sc + 1] = t;
  74                         break;
  75                     }
  76
  77                     case 'L': {
  78                         int t = sperm[sr * c + sc];
  79                         sperm[sr * c + sc] = sperm[sr * c + sc + 1];
  80                         sperm[sr * c + sc + 1] = sperm[(sr + 1) * c + sc + 1];
  81                         sperm[(sr + 1) * c + sc + 1] = sperm[(sr + 1) * c + sc];
  82                         sperm[(sr + 1) * c + sc] = t;
  83                         break;
  84                     }
  85                 }
  86                 --amount;
  87             }
  88         return new StepDescription(sperm, snumWrites);
  89     }
  90
  91
  92     public static void main(String[] args) throws InterruptedException {
  93         Thread thread = new Thread(new garbling_petr_slow());
  94         thread.start();
  95         thread.join();
  96     }
  97
  98     static final String TASK_ID = "garbling";
  99     static final String IN_FILE = TASK_ID + ".in";
 100     static final String OUT_FILE = TASK_ID + ".out";
 101     BufferedReader reader;
 102     StringTokenizer tokenizer;
 103     PrintWriter writer;
 104
 105     public void run() {
 106         try {
 107             reader = new BufferedReader(new FileReader(IN_FILE));
 108             tokenizer = null;
 109             writer = new PrintWriter(OUT_FILE);
 110             solve();
 111             reader.close();
 112             writer.close();
 113         } catch (Exception e) {
 114             e.printStackTrace();
 115             System.exit(1);
 116         }
 117     }
 118
 119     int nextInt() throws IOException {
 120         return Integer.parseInt(nextToken());
 121     }
 122
 123     long nextLong() throws IOException {
 124         return Long.parseLong(nextToken());
 125     }
 126
 127     double nextDouble() throws IOException {
 128         return Double.parseDouble(nextToken());
 129     }
 130
 131     String nextToken() throws IOException {
 132         while (tokenizer == null || !tokenizer.hasMoreTokens()) {
 133             tokenizer = new StringTokenizer(reader.readLine());
 134         }
 135         return tokenizer.nextToken();
 136     }
 137 }