結果

問題 No.5002 stick xor
ユーザー tsukammotsukammo
提出日時 2018-05-26 00:08:36
言語 Java
(openjdk 23)
結果
AC  
実行時間 968 ms / 1,000 ms
コード長 4,683 bytes
コンパイル時間 35,841 ms
実行使用メモリ 24,108 KB
スコア 36,789
最終ジャッジ日時 2018-05-26 00:09:14
ジャッジサーバーID
(参考情報)
judge8 /
純コード判定しない問題か言語
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import java.io.IOException;
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;
int[] L;
boolean[][] map;
Rect[] rs;
void solve() {
input();
init();
simulate(); // new
if (submit) {
output();
}
}
void init() {
rs = new Rect[K];
for (int i = 0; i < K; i++) {
rs[i] = new Rect(i, L[i] - 1);
}
if (submit) {
return;
}
}
void simulate() {
System.err.println("First:" + (first));
int 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;
}
int id = rnd.nextInt(K);
Rect r = rs[id];
int x = rnd.nextInt(N);
int y = rnd.nextInt(N);
int d = rnd.nextInt(2);
int ex = x + r.w * dx[d];
int ey = y + r.w * dy[d];
if (outMap(ex, ey)) {
d = d + 2;
}
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];
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];
ex += dx[d];
ey += dy[d];
}
}
c++;
}
score = evalAll();
System.err.println("End :" + (score));
System.err.println("Last :" + (first - score) + " loop:" + c + " up:" + u);
}
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 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(2);
int ex = x + w * dx[d];
int ey = y + w * dy[d];
if (outMap(ex, ey)) {
d = 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;
}
}
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 = 10000;
static final long TL = 800;
static boolean submit = true;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0