結果
| 問題 | No.5002 stick xor |
| ユーザー |
 threepipes_s
|
| 提出日時 | 2018-05-29 03:16:46 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 10,748 bytes |
| コンパイル時間 | 6,904 ms |
| 実行使用メモリ | 20,536 KB |
| スコア | 0 |
| 最終ジャッジ日時 | 2018-05-29 03:16:54 |
|
ジャッジサーバーID （参考情報） |
judge9 / |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | -- | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
ソースコード
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();
}
void solveByTest() {
int sum = 0;
for (int i = 0; i < 32; i++) {
genTest(i);
int res = 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() {
String ans = "";
for (int i = 0; i < k; i++) {
final int idx = lt[i];
if(ld[idx] == 0) ans += String.format("%d %d %d %d\n", ly[idx] + 1, lx[idx] + 1, ly[idx] + 1, lx[idx] + l[idx]);
else ans += String.format("%d %d %d %d\n", ly[idx] + 1, lx[idx] + 1, ly[idx] + l[idx], lx[idx] + 1);
}
out.println(ans);
}
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.1) {
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.1;
int sa() {
final int MAX_ITER = 7000000;
Random rand = new Random(0);
int score = 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);
// String output = "";
// if (nextScore > 0) {
// output += ("Update! ");
// }
double temperature = temper((double) i / MAX_ITER);
double prob = prob(nextScore, temperature);
if(rand.nextDouble() <= prob) {
score += nextScore;
applyNext();
// output += "swap " + nextScore;
// out.println(output);
// out.flush();
}
}
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;
}
@Override
public 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();}
}