結果
問題 | No.5002 stick xor |
ユーザー |
![]() |
提出日時 | 2018-05-29 03:54:21 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 801 ms / 1,000 ms |
コード長 | 10,505 bytes |
コンパイル時間 | 31,217 ms |
実行使用メモリ | 23,440 KB |
スコア | 29,345 |
最終ジャッジ日時 | 2018-05-29 03:54:55 |
ジャッジサーバーID (参考情報) |
judge6 / |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 32 |
ソースコード
import java.io.*;import java.util.*;public class Main implements Runnable {static ContestScanner in;static Writer out;public static void main(String[] args) {new Thread(null, new Main(), "", 16 * 1024 * 1024).start();}public void run() {Main main = new Main();try {in = new ContestScanner();out = new Writer();main.solve();out.close();in.close();} catch (IOException e) {e.printStackTrace();}}int[] l, lt;long[] mask;int[] lx, ly, ld;long[][] map;int n, k;void solve() throws IOException {genTestIO();sa();output();// solveByTest();}void solveByTest() {int sum = 0;for (int i = 0; i < 32; i++) {genTest(i);int res = solveGreedy() + sa();sum += res;System.out.println(res);}System.out.println("Score: " + sum);// output();// for (int i = 0; i < n; i++) {// for (int j = 0; j < n; j++) {// System.out.print((map[i][0] >> j) & 1);// System.out.print(" ");// }// System.out.println();// }}void output() {for (int i = 0; i < k; i++) {final int idx = lt[i];if(ld[idx] == 0) out.println(String.format("%d %d %d %d", ly[idx] + 1, lx[idx] + 1, ly[idx] + 1, lx[idx] + l[idx]));else out.println(String.format("%d %d %d %d", ly[idx] + 1, lx[idx] + 1, ly[idx] + l[idx], lx[idx] + 1));}}void genTest(long seed) {boolean debug = false;Random rand = new Random(seed);n = 60;k = 500;l = new int[k];lt = new int[k];lx = new int[k];ly = new int[k];ld = new int[k];mask = new long[k];Pair[] p = new Pair[k];if (debug) out.println(n + " " + k);for (int i = 0; i < k; i++) {l[i] = rand.nextInt(25) + 1;p[i] = new Pair(-l[i], i);if (debug) {if (i > 0) out.print(" ");out.print(l[i]);}}Arrays.sort(p);for (int i = 0; i < k; i++) {l[i] = -p[i].a;mask[i] = (1L << l[i]) - 1;lt[p[i].b] = i;}if (debug) out.println();map = new long[n][2];for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {long a = rand.nextInt(2);map[i][0] |= a << j;map[j][1] |= a << i;if (debug)out.print(a);}if (debug)out.println();}}void genTestIO() throws IOException {n = in.nextInt();k = in.nextInt();l = new int[k];lt = new int[k];lx = new int[k];ly = new int[k];ld = new int[k];mask = new long[k];for (int i = 0; i < k; i++) {l[i] = in.nextInt();lt[i] = i;mask[i] = (1L << l[i]) - 1;}map = new long[n][2];for (int i = 0; i < n; i++) {char[] s = in.nextToken().toCharArray();for (int j = 0; j < n; j++) {long a = s[j] - '0';map[i][0] |= a << j;map[j][1] |= a << i;}}}int solveGreedy() {int cnt = 0;for (int i = 0; i < k; i++) {int max = Integer.MIN_VALUE;int maxPos = 0;int maxV = 0;for (int j = 0; j < n; j++) {for (int m = 0; m < n - l[i]; m++) {for (int d = 0; d < 2; d++) {int res = check(d, j, m, i, map);if (res > max) {max = res;maxPos = j * n + m;maxV = d;}}}}cnt += max;setLPos(maxV, maxPos / n, maxPos % n, i);apply(maxV, maxPos / n, maxPos % n, i, map);}return cnt;}/*** @param v 縦横* @param y y座標(実際のもの)* @param x x座標(実際のもの)* @param id 利用する棒のid*/void applyReal(int v, int y, int x, int id, long[][] map) {if (v == 1) apply(v, x, y, id, map);else apply(v, y, x, id, map);}void apply(int v, int y, int x, int id, long[][] map) {map[y][v] ^= mask[id] << x;for (int i = 0; i < l[id]; i++) {map[i + x][v^1] ^= 1L << y;}}void setLPos(int v, int y, int x, int id) {if (v == 1) {int tmp = y;y = x;x = tmp;}ld[id] = v;ly[id] = y;lx[id] = x;}int checkReal(int v, int y, int x, int id, long[][] map) {if (v == 1) return check(v, x, y, id, map);else return check(v, y, x, id, map);}int check(int v, int y, int x, int id, long[][] map) {return Long.bitCount(map[y][v]) - Long.bitCount(map[y][v] ^ (mask[id] << x));}int checkDoubleReal(int v, int y1, int x1, int y2, int x2, int id, long[][] map) {if (v == 1) return checkDouble(v, x1, y1, x2, y2, id, map);else return checkDouble(v, y1, x1, y2, x2, id, map);}int checkDouble(int v, int y1, int x1, int y2, int x2, int id, long[][] map) {if (y1 == y2) {return Long.bitCount(map[y1][v]) - Long.bitCount(map[y1][v] ^ (mask[id] << x1) ^ (mask[id] << x2));} else {return check(v, y1, x1, id, map) + check(v, y2, x2, id, map);}}int tld, tly, tlx, tid;int next(Random rand, int vol) {tid = rand.nextInt(k);int score;if (rand.nextDouble() < 0.01) {tld = ld[tid] ^ 1;tlx = lx[tid];tly = ly[tid];if (tld == 0) {if (lx[tid] + l[tid] >= n) tlx = n - l[tid];} else {if (ly[tid] + l[tid] >= n) tly = n - l[tid];}final long cp = (map[ly[tid]][0] >> lx[tid]) & 1;score = checkReal(ld[tid], ly[tid], lx[tid], tid, map)+ checkReal(tld, tly, tlx, tid, map) + (cp == 1 ? -2 : 2);} else {final int mvol = rand.nextInt(vol) + 1;final int yvol = rand.nextInt(mvol);final int xvol = mvol - yvol;int minY = Math.max(0, ly[tid] - yvol);final int maxY = Math.min(n - (ld[tid] == 0 ? 1 : l[tid]), ly[tid] + yvol);minY = Math.min(minY, maxY);tly = rand.nextInt(maxY - minY + 1) + minY;int minX = Math.max(0, lx[tid] - xvol);final int maxX = Math.min(n - (ld[tid] == 0 ? l[tid] : 1), lx[tid] + xvol);minX = Math.min(minX, maxX);tlx = rand.nextInt(maxX - minX + 1) + minX;score = checkDoubleReal(ld[tid], ly[tid], lx[tid], tly, tlx, tid, map);tld = ld[tid];}return score;}void applyNext() {applyReal(ld[tid], ly[tid], lx[tid], tid, map);ld[tid] = tld;ly[tid] = tly;lx[tid] = tlx;applyReal(ld[tid], ly[tid], lx[tid], tid, map);}double temper(double r) {return Math.pow(TEMPER, r);}double prob(double nextScore, double temper) {if(0 <= nextScore) return 1;else return Math.pow(Math.E, nextScore / temper);}final double TEMPER = 0.15;int sa() {final int MAX_ITER = 1500000;Random rand = new Random(0);int score = 0;//init(rand);for (int i = 0; i < MAX_ITER; i++) {int vol = Math.max(1, (MAX_ITER - i) * 20 / MAX_ITER);int nextScore = next(rand, vol);double temperature = temper((double) i / MAX_ITER);double prob = prob(nextScore, temperature);if(rand.nextDouble() <= prob) {score += nextScore;applyNext();}}return score;}int init(Random rand) {int score = 0;for (int i = 0; i < k; i++) {ld[i] = rand.nextInt(2);final int maxY = n - (ld[i] == 0 ? 1 : l[i]);final int maxX = n - (ld[i] == 0 ? l[i] : 1);ly[i] = rand.nextInt(maxY + 1);lx[i] = rand.nextInt(maxX + 1);score += checkReal(ld[i], ly[i], lx[i], i, map);applyReal(ld[i], ly[i], lx[i], i, map);}return score;}}class Pair implements Comparable<Pair> {int a, b;Pair(int a, int b) {this.a = a;this.b = b;}@Overridepublic int compareTo(Pair o) {if (a != o.a) return a - o.a;return b - o.b;}}class Writer extends PrintWriter{public Writer(String filename)throws IOException{super(new BufferedWriter(new FileWriter(filename)));}public Writer()throws IOException {super(System.out);}}class ContestScanner implements Closeable {private BufferedReader in;private int c=-2;public ContestScanner()throws IOException{in=new BufferedReader(new InputStreamReader(System.in));}public ContestScanner(String filename)throws IOException{in=new BufferedReader(new InputStreamReader(new FileInputStream(filename)));}public String nextToken()throws IOException {StringBuilder sb=new StringBuilder();while((c=in.read())!=-1&&Character.isWhitespace(c));while(c!=-1&&!Character.isWhitespace(c)){sb.append((char)c);c=in.read();}return sb.toString();}public String readLine()throws IOException{StringBuilder sb=new StringBuilder();if(c==-2)c=in.read();while(c!=-1&&c!='\n'&&c!='\r'){sb.append((char)c);c=in.read();}return sb.toString();}public long nextLong()throws IOException,NumberFormatException{return Long.parseLong(nextToken());}public int nextInt()throws NumberFormatException,IOException{return(int)nextLong();}public double nextDouble()throws NumberFormatException,IOException{return Double.parseDouble(nextToken());}public void close() throws IOException {in.close();}}