結果
| 問題 |
No.5002 stick xor
|
| コンテスト | |
| ユーザー |
 ziita
|
| 提出日時 | 2018-05-26 17:47:09 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 965 ms / 1,000 ms |
| コード長 | 11,221 bytes |
| コンパイル時間 | 34,463 ms |
| 実行使用メモリ | 20,996 KB |
| スコア | 43,347 |
| 最終ジャッジ日時 | 2018-05-26 17:47:45 |
|
ジャッジサーバーID （参考情報） |
judge9 / |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 32 |
ソースコード
import java.io.*;
import java.util.*;
import java.math.*;
// import java.awt.Point;
public class Main {
InputStream is;
PrintWriter out;
String INPUT = "";
long mod = 1_000_000_007;
long inf = Long.MAX_VALUE;
long start = System.currentTimeMillis();
int n,k;
int count = 0;
int change = 0;
double[] log = new double[131072];
SplittableRandom rnd = new SplittableRandom(1972);
long timeLimit = 850;
long timeout2 = System.currentTimeMillis() + timeLimit * 10 / 10;
void solve(){
n = ni();
k = ni();
int[] L = new int[k];
int[] L2 = new int[k];
for(int i = 0; i < k; i++){
L[i] = ni();
L2[i] = L[i];
}
// Arrays.sort(L2);
// for(int i = 0; i < k/2; i++){
// int tmp = L2[i];
// L2[i] = L2[k-1-i];
// L2[k-1-i] = tmp;
// }
for (int i = 0; i < log.length; i++) {
log[i] = Math.log((i + 0.5) / log.length);
}
int[][] map = new int[n][n];
for(int i = 0; i < n; i++){
char[] c = ns().toCharArray();
for(int j = 0; j < n; j++){
map[i][j] = c[j]-'0';
}
}
int[][] ans = new int[k][4];
boolean[] seen = new boolean[k];
for(int line = 0; line < k; line++){
if(L[line]<=10) continue;
int[] res = find_greedy(map, L[line]);
if(res[0]>=0){
reload_map(map, ans, res, line);
seen[line] = true;
}
}
for(int line = 0; line < k; line++){
if(seen[line]||L[line]<=2) continue;
int[] res = find_greedy(map, L[line]);
if(res[0]>=0){
reload_map(map, ans, res, line);
seen[line] = true;
}
}
for(int line = 0; line < k; line++){
if(seen[line]) continue;
int[] res = find_greedy(map, L[line]);
if(res[0]>=0){
reload_map(map, ans, res, line);
seen[line] = true;
}
}
anealing(map, ans);
System.err.println(count+" "+change);
print_ans(ans, L);
}
void anealing(int[][] map, int[][] ans){
long duration = timeout2 - System.currentTimeMillis();
double K = 0.1;//TODO
double rem = duration * K;
while(true){
if (count%3 == 0) {
long t = System.currentTimeMillis();
if (t >= timeout2) break;
rem = (timeout2 - t) * K / duration;
}
count++;
int id = rnd.nextInt(k);
int line_length = ans[id][2]-ans[id][0]+ans[id][3]-ans[id][1]+1;
int beforescore = 0;
if(ans[id][0]==ans[id][2]){
for(int j = ans[id][1]; j <= ans[id][3]; j++){
if(map[ans[id][0]][j]==0) beforescore++;
map[ans[id][0]][j] = 1-map[ans[id][0]][j];
}
}
else{
for(int j = ans[id][0]; j <= ans[id][2]; j++){
if(map[j][ans[id][1]]==0) beforescore++;
map[j][ans[id][1]] = 1-map[j][ans[id][1]];
}
}
for(int k = 0; k < 5; k++){
int x = rnd.nextInt(n);
int ys = rnd.nextInt(n-line_length);
int score = 0;
for(int j = ys; j < ys+line_length; j++){
if(map[x][j]==1) score++;
}
double difscore = score-beforescore;
if(difscore >= 0 || difscore > log[rnd.nextInt(log.length)] * rem){
if(difscore>0)System.err.println(count+" "+difscore);
change++;
ans[id][0] = x;
ans[id][1] = ys;
ans[id][2] = x;
ans[id][3] = ys+line_length-1;
if(difscore>0) break;
}
int xs = rnd.nextInt(n-line_length);
int y = rnd.nextInt(n);
score = 0;
for(int j = xs; j < xs+line_length; j++){
if(map[j][y]==1) score++;
}
difscore = score-beforescore;
if(difscore >= 0 || difscore > log[rnd.nextInt(log.length)] * rem){
change++;
ans[id][0] = xs;
ans[id][1] = y;
ans[id][2] = xs+line_length-1;
ans[id][3] = y;
if(difscore>0) break;
}
}
if(ans[id][0]==ans[id][2]){
for(int j = ans[id][1]; j <= ans[id][3]; j++){
map[ans[id][0]][j] = 1-map[ans[id][0]][j];
}
}
else{
for(int j = ans[id][0]; j <= ans[id][2]; j++){
map[j][ans[id][1]] = 1-map[j][ans[id][1]];
}
}
}
}
void print_ans(int[][] ans, int[] L){
int[][] list = new int[n][n];
int[] idx = new int[n];
for(int i = 0; i < k; i++){
int dist = ans[i][2]-ans[i][0]+ans[i][3]-ans[i][1]+1;
int p = idx[dist];
list[dist][p] = i;
idx[dist]++;
}
for(int i = 0; i < n; i++) idx[i] = 0;
for(int i = 0; i < k; i++){
// idx[L[i]]--;
int p = idx[L[i]];
int id = list[L[i]][p];
idx[L[i]]++;
for(int j = 0; j < 4 ;j++){
out.print((ans[id][j]+1)+" ");
}
out.println();
}
}
void reload_map(int[][] map, int[][] ans, int[] res, int line){
ans[line][0] = res[0];
ans[line][1] = res[1];
ans[line][2] = res[2];
ans[line][3] = res[3];
if(res[0]==res[2]){
for(int j = res[1]; j <= res[3]; j++){
map[res[0]][j] = 1 - map[res[0]][j];
}
}
else{
for(int j = res[0]; j <= res[2]; j++){
map[j][res[1]] = 1 - map[j][res[1]];
}
}
}
int[] find_lublack(int[][] map, int line_length){
int[] res = new int[4];
Arrays.fill(res, -1);
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(map[i][j]==1 && n-j>=line_length){
res[0] = i;
res[1] = j;
res[2] = i;
res[3] = j+line_length-1;
return res;
}
}
}
return res;
}
int[] find_greedy(int[][] map, int line_length){
int score = -100;
int[] res = new int[4];
Arrays.fill(res, -1);
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
int tmpscore = 0;
boolean flag = true;
for(int k = 0; k < line_length; k++){
if(j+k>=n){
flag = false;
break;
}
if(map[i][j+k]==1) tmpscore++;
else tmpscore--;
}
if(flag && tmpscore>score){
score = tmpscore;
res[0] = i;
res[1] = j;
res[2] = i;
res[3] = j+line_length-1;
}
tmpscore = 0;
flag = true;
for(int k = 0; k < line_length; k++){
if(i+k>=n){
flag = false;
break;
}
if(map[i+k][j]==1) tmpscore++;
else tmpscore--;
}
if(flag && tmpscore>score){
score = tmpscore;
res[0] = i;
res[1] = j;
res[2] = i+line_length-1;
res[3] = j;
}
}
}
return res;
}
void run() throws Exception
{
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
}
public static void main(String[] args) throws Exception { new Main().run(); }
private byte[] inbuf = new byte[1024];
private int lenbuf = 0, ptrbuf = 0;
private int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
private double nd() { return Double.parseDouble(ns()); }
private char nc() { return (char)skip(); }
private String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b) && b != ' ')){
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}
private int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}
private int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}