NEERC/garbling/garbling_rs.java

   1 import java.io.*;
   2 import java.util.*;
   3 import java.math.BigInteger;
   4
   5 public class garbling_rs implements Runnable {
   6     private BufferedReader in;
   7     private PrintWriter out;
   8
   9     private void check(boolean expr, String msg) {
  10         if (!expr) {
  11             throw new Error(msg);
  12         }
  13     }
  14
  15     private void checkBounds(long n, long low, long hi, String nStr) {
  16         check((low <= n) && (n <= hi), nStr + " is not in [" + low + ", " + hi + "]");
  17     }
  18
  19     private int r, c;
  20     private char[][] map;
  21     private int[] fTemp, fSingle;
  22     private int[] aTemp, aSingle;
  23     private static final int modulo = 100000;
  24
  25     private void applySingle(int[] f, int[] a, int n) {
  26         int count = 0;
  27         for (int i = 0; i < r - 1; i++) {
  28             for (int j = 0; j < c - 1; j++) {
  29                 if (count++ >= n) {
  30                     return;
  31                 }
  32                 int p11 = i * c + j;
  33                 int p12 = p11 + 1;
  34                 int p21 = p11 + c;
  35                 int p22 = p11 + c + 1;
  36
  37                 a[f[p11]]++;
  38                 while (a[f[p11]] >= modulo) {
  39                     a[f[p11]] -= modulo;
  40                 }
  41                 if (map[i][j] == 'L') {
  42                     int tmp = f[p11];
  43                     f[p11] = f[p12];
  44                     f[p12] = f[p22];
  45                     f[p22] = f[p21];
  46                     f[p21] = tmp;
  47                 } else if (map[i][j] == 'R') {
  48                     int tmp = f[p11];
  49                     f[p11] = f[p21];
  50                     f[p21] = f[p22];
  51                     f[p22] = f[p12];
  52                     f[p12] = tmp;
  53                 }
  54             }
  55         }
  56     }
  57
  58     private void inversePerm(int[] f) {
  59         for (int i = 0; i < f.length; i++) {
  60             fTemp[f[i]] = i;
  61         }
  62         System.arraycopy(fTemp, 0, f, 0, f.length);
  63     }
  64
  65     private void apply(BigInteger n, int[] f, int[] a) {
  66         if (n.equals(BigInteger.ZERO)) {
  67             for (int i = 0; i < f.length; i++) {
  68                 f[i] = i;
  69                 a[i] = 0;
  70             }
  71             return;
  72         }
  73         apply(n.shiftRight(1), f, a);
  74         for (int i = 0; i < f.length; i++) {
  75             fTemp[i] = f[f[i]];
  76             aTemp[i] = a[i] + a[f[i]];
  77             if (aTemp[i] >= modulo) {
  78                 aTemp[i] -= modulo;
  79             }
  80         }
  81         System.arraycopy(fTemp, 0, f, 0, f.length);
  82         System.arraycopy(aTemp, 0, a, 0, a.length);
  83         if (n.testBit(0)) {
  84             for (int i = 0; i < f.length; i++) {
  85                 fTemp[i] = f[fSingle[i]];
  86                 aTemp[i] = aSingle[i] + a[fSingle[i]];
  87                 if (aTemp[i] >= modulo) {
  88                     aTemp[i] -= modulo;
  89                 }
  90             }
  91             System.arraycopy(fTemp, 0, f, 0, f.length);
  92             System.arraycopy(aTemp, 0, a, 0, a.length);
  93         }
  94     }
  95
  96     private void solve() throws IOException {
  97         StringTokenizer st = new StringTokenizer(in.readLine());
  98         r = Integer.parseInt(st.nextToken());
  99         c = Integer.parseInt(st.nextToken());
 100         BigInteger n = new BigInteger(st.nextToken());
 101         checkBounds(r, 2, 300, "r");
 102         checkBounds(c, 2, 300, "c");
 103         check(n.compareTo(BigInteger.ZERO) >= 0, "n is negative");
 104         check(n.compareTo(BigInteger.TEN.pow(100)) < 0, "n is greater than 10^{100}");
 105         map = new char[r - 1][];
 106         for (int i = 0; i < r - 1; i++) {
 107             String line = in.readLine();
 108             check(line.length() == c - 1, "Invalid size of map");
 109             map[i] = line.toCharArray();
 110             for (int j = 0; j < c - 1; j++) {
 111                 check(map[i][j] == 'L' || map[i][j] == 'R' || map[i][j] == 'N', "invalid character in map");
 112             }
 113         }
 114
 115         fTemp = new int[r * c];
 116         aTemp = new int[r * c];
 117         int[] f = new int[r * c];
 118         int[] a = new int[r * c];
 119         int block = (r - 1) * (c - 1);
 120
 121         fSingle = new int[r * c];
 122         aSingle = new int[r * c];
 123         for (int i = 0; i < f.length; i++) {
 124             fSingle[i] = i;
 125             aSingle[i] = 0;
 126         }
 127         applySingle(fSingle, aSingle, block);
 128         inversePerm(fSingle);
 129
 130         apply(n.divide(BigInteger.valueOf(block)), f, a);
 131         inversePerm(f);
 132         applySingle(f, a, n.mod(BigInteger.valueOf(block)).intValue());
 133         for (int i = 0; i < f.length; i++) {
 134             out.println(a[i]);
 135         }
 136     }
 137
 138     public static void main(String[] args) {
 139         new Thread(new garbling_rs()).start();
 140     }
 141
 142     public void run() {
 143         String problem = getClass().getName().split("_")[0];
 144         try {
 145             in = new BufferedReader(new FileReader(new File(problem + ".in")));
 146             out = new PrintWriter(new File(problem + ".out"));
 147             solve();
 148             in.close();
 149             out.close();
 150         } catch (IOException e) {
 151             e.printStackTrace();
 152             System.exit(1);
 153         }
 154     }
 155 }