結果
問題 | No.5002 stick xor |
ユーザー | tsukammo |
提出日時 | 2018-05-28 20:08:39 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 958 ms / 1,000 ms |
コード長 | 6,938 bytes |
コンパイル時間 | 35,753 ms |
実行使用メモリ | 24,592 KB |
スコア | 41,201 |
最終ジャッジ日時 | 2018-05-28 20:09:16 |
ジャッジサーバーID (参考情報) |
judge9 / |
純コード判定しない問題か言語 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 923 ms
24,584 KB |
testcase_01 | AC | 937 ms
24,572 KB |
testcase_02 | AC | 928 ms
24,584 KB |
testcase_03 | AC | 927 ms
24,584 KB |
testcase_04 | AC | 958 ms
23,524 KB |
testcase_05 | AC | 930 ms
24,580 KB |
testcase_06 | AC | 936 ms
24,580 KB |
testcase_07 | AC | 925 ms
24,580 KB |
testcase_08 | AC | 927 ms
24,588 KB |
testcase_09 | AC | 930 ms
24,584 KB |
testcase_10 | AC | 929 ms
23,536 KB |
testcase_11 | AC | 934 ms
24,576 KB |
testcase_12 | AC | 926 ms
24,580 KB |
testcase_13 | AC | 927 ms
24,584 KB |
testcase_14 | AC | 926 ms
24,588 KB |
testcase_15 | AC | 927 ms
24,572 KB |
testcase_16 | AC | 927 ms
23,548 KB |
testcase_17 | AC | 925 ms
24,588 KB |
testcase_18 | AC | 933 ms
24,580 KB |
testcase_19 | AC | 941 ms
24,572 KB |
testcase_20 | AC | 926 ms
24,576 KB |
testcase_21 | AC | 956 ms
23,580 KB |
testcase_22 | AC | 926 ms
24,580 KB |
testcase_23 | AC | 932 ms
24,576 KB |
testcase_24 | AC | 926 ms
24,588 KB |
testcase_25 | AC | 927 ms
24,572 KB |
testcase_26 | AC | 927 ms
24,584 KB |
testcase_27 | AC | 925 ms
24,592 KB |
testcase_28 | AC | 925 ms
24,576 KB |
testcase_29 | AC | 922 ms
24,576 KB |
testcase_30 | AC | 927 ms
23,536 KB |
testcase_31 | AC | 924 ms
24,584 KB |
ソースコード
import java.io.IOException; import java.util.ArrayList; import java.util.BitSet; import java.util.Collections; import java.util.Deque; import java.util.List; import java.util.Scanner; /** * yukicoder * * @author tsukammo */ public class Main { Scanner sc = new Scanner(System.in); Random rnd = new Random(19881221L); long st, et; int first; public static void main(String[] args) throws IOException { new Main().solve(); } // 制約 static int N = 60, K = 500, NN = N * N, W = 25; int[] L; boolean[][] map; Rect[] rs; List<Rect> rlist; Deque<Node> nstack; void solve() { input(); init(); simulate(); // new if (submit) { output(); } } void init() { rs = new Rect[K]; rlist = new ArrayList<Rect>(); for (int i = 0; i < K; i++) { Rect tmp = new Rect(i, L[i] - 1); rs[i] = tmp; rlist.add(tmp); } Collections.sort(rlist); if (submit) { return; } } void simulate() { System.err.println("First:" + (first)); int score = first; for (Rect r : rlist) { int max = -100; // row for (int i = 0; i < N; i++) { int sum = 0; for (int x = 0; x <= r.w; x++) { sum += map[i][x] ? 1 : -1; } if (max <= sum) { max = sum; r.y = i; r.x = 0; r.d = 0; } for (int j = 1; j < N - r.w; j++) { sum += map[i][j + r.w] ? 1 : -1; sum -= map[i][j - 1] ? 1 : -1; if (max <= sum) { max = sum; r.y = i; r.x = j; r.d = 0; } } } // col for (int j = 0; j < N; j++) { int sum = 0; for (int y = 0; y <= r.w; y++) { sum += map[y][j] ? 1 : -1; } if (max < sum) { max = sum; r.y = 0; r.x = j; r.d = 1; } for (int i = 1; i < N - r.w; i++) { sum += map[i + r.w][j] ? 1 : -1; sum -= map[i - 1][j] ? 1 : -1; if (max < sum) { max = sum; r.y = i; r.x = j; r.d = 1; } } } // update score -= max; int ex = r.x; int ey = r.y; // flip for (int i = 0; i <= r.w; i++) { map[ey][ex] = !map[ey][ex]; ex += dx[r.d]; ey += dy[r.d]; } } System.err.println("End :" + (score)); score = evalAll(); System.err.println("Start:" + (score)); long currentTime = System.currentTimeMillis(); double C = TEMP * TL; double Line = 0.0; int tmpScore = 0; int c = 0, u = 0; while (currentTime < et) { if (c % 1000 == 0) { currentTime = System.currentTimeMillis(); Line = (et - currentTime) / C; } c++; int id = rnd.nextInt(rlist.size()); Rect r = rs[id]; int d = rnd.nextInt(2); int x, y; if (d == 0) { x = rnd.nextInt(N - r.w); y = rnd.nextInt(N); } else { x = rnd.nextInt(N); y = rnd.nextInt(N - r.w); } int ex = x + r.w * dx[d]; int ey = y + r.w * dy[d]; tmpScore = evalChange(x, y, d, r); if (tmpScore <= 0 || Line > tmpScore * rnd.nextDouble()) { score += tmpScore; // update r.x = x; r.y = y; r.d = d; if (tmpScore < 0) { u++; } //System.err.println("update:" + score); } else { // rollback // before ex = r.x; ey = r.y; for (int i = 0; i <= r.w; i++) { map[ey][ex] = !map[ey][ex]; //map.flip(ey * N + ex); ex += dx[r.d]; ey += dy[r.d]; } // after ex = x; ey = y; for (int i = 0; i <= r.w; i++) { map[ey][ex] = !map[ey][ex]; //map.flip(ey * N + ex); ex += dx[d]; ey += dy[d]; } } } System.err.println("End :" + (score)); score = evalAll(); System.err.println("End :" + (score)); System.err.println("Last :" + (first - score)); } int evalChange(int x, int y, int d, Rect r) { int ret = 0; // before int ex = r.x; int ey = r.y; for (int i = 0; i <= r.w; i++) { if (map[ey][ex]) { ret--; } else { ret++; } map[ey][ex] = !map[ey][ex]; ex += dx[r.d]; ey += dy[r.d]; } // after ex = x; ey = y; for (int i = 0; i <= r.w; i++) { if (map[ey][ex]) { ret--; } else { ret++; } map[ey][ex] = !map[ey][ex]; ex += dx[d]; ey += dy[d]; } return ret; } int evalAll() { int ret = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (map[i][j]) { ret++; } } } return ret; } final static int dx[] = new int[] { 1, 0, -1, 0 }; final static int dy[] = new int[] { 0, 1, 0, -1 }; boolean outMap(int x, int y) { return !(x > -1 && y > -1 && x < N && y < N); } void input() { N = sc.nextInt(); st = System.currentTimeMillis(); et = st + TL; K = sc.nextInt(); L = new int[K]; for (int i = 0; i < K; i++) { L[i] = sc.nextInt(); } sc.nextLine(); map = new boolean[N][N]; first = 0; for (int i = 0; i < N; i++) { String tmp = sc.nextLine(); char[] cl = tmp.toCharArray(); for (int j = 0; j < N; j++) { if (cl[j] == '1') { map[i][j] = true; first++; } } } } class Node implements Comparable<Node> { BitSet map; Rect[] rs; int score; int nextRecNo; public Node(BitSet map) { this.map = (BitSet) map.clone(); this.rs = new Rect[K]; score = map.cardinality(); nextRecNo = 0; } public Node(Node n) { this.score = n.score; this.map = (BitSet) n.map.clone(); this.nextRecNo = n.nextRecNo; } @Override public int compareTo(Node o) { return Integer.compare(this.score, o.score); } } class Rect implements Comparable<Rect> { int id; int x, y, d; int w; public Rect(int id, int w) { this.id = id; this.w = w; /* this.x = rnd.nextInt(N); this.y = rnd.nextInt(N); this.d = rnd.nextInt(4); int ex = x + w * dx[d]; int ey = y + w * dy[d]; if (outMap(ex, ey)) { if (outMap(ex, ey)) { if (d > 1) { d -= 2; } else { d += 2; } } } ex = x; ey = y; // flip for (int i = 0; i <= w; i++) { map[ey][ex] = !map[ey][ex]; ex += dx[d]; ey += dy[d]; } */ } public String toString() { int sx = x + 1; int sy = y + 1; int ex = sx + w * dx[d]; int ey = sy + w * dy[d]; if (d > 1) { sx = ex; sy = ey; d -= 2; ex = sx + w * dx[d]; ey = sy + w * dy[d]; } return sy + " " + sx + " " + ey + " " + ex; } @Override public int compareTo(Rect o) { return Integer.compare(o.w, this.w); } } class Random { private long seed; private final long multiplier = 0x5DEECE66DL, addend = 0xBL, mask = (1L << 48) - 1; int bits, val; Random(long seed) { this.seed = seed; } int nextInt(int n) { do { bits = (int) ((seed = (seed * multiplier + addend) & mask) >>> 17); val = bits % n; } while (bits - val + (n - 1) < 0); return val; } double nextDouble() { return nextInt(10000000) / 10000000.0; } } void output() { for (int i = 0; i < K; i++) { System.out.println(rs[i].toString()); } } final double TEMP = 100000; static final long TL = 800; static boolean submit = true; }