結果
| 問題 |
No.5002 stick xor
|
| コンテスト | |
| ユーザー |
 ziita
|
| 提出日時 | 2018-05-26 11:21:07 |
| 言語 | Java (openjdk 23) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 9,246 bytes |
| コンパイル時間 | 40,273 ms |
| スコア | 0 |
| 最終ジャッジ日時 | 2018-05-26 11:21:50 |
|
ジャッジサーバーID （参考情報） |
judge8 / |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | TLE * 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;
void solve(){
n = ni();
k = ni();
int[] L = new int[k];
for(int i = 0; i < k; i++){
L[i] = ni();
}
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];
for(int line = 0; line < k; line++){
int[] res = find_greedy(map, L[line]);
if(res[0]>=0){
reload_map(map, ans, res, line);
}
}
anealing(map, ans);
System.err.println(count);
print_ans(ans);
}
void anealing(int[][] map, int[][] ans){
Random rnd = new Random();
while(System.currentTimeMillis()-start<=950){
count++;
int id = rnd.nextInt(k);
int dir = rnd.nextInt(2);
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++;
else 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++;
else beforescore--;
map[j][ans[id][1]] = 1-map[j][ans[id][1]];
}
}
if(dir==0){
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++;
else score--;
}
// System.err.println(id+" "+score+" "+beforescore);
if(score>beforescore){
ans[id][0] = x;
ans[id][1] = ys;
ans[id][2] = x;
ans[id][3] = ys+line_length-1;
}
}
if(dir==1){
int xs = rnd.nextInt(n-line_length);
int y = rnd.nextInt(n);
int score = 0;
for(int j = xs; j < xs+line_length; j++){
if(map[j][y]==1) score++;
else score--;
}
// System.err.println(id+" "+score+" "+beforescore);
if(score>beforescore){
ans[id][0] = xs;
ans[id][1] = y;
ans[id][2] = xs+line_length-1;
ans[id][3] = y;
}
}
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){
for(int i = 0; i < k; i++){
for(int j = 0; j < 4; j++){
out.print((ans[i][j]+1)+" ");
}
out.println();
}
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)); }
}