結果

問題 No.5002 stick xor
ユーザー kuuso1kuuso1
提出日時 2018-05-26 00:01:10
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 924 ms / 1,000 ms
コード長 7,498 bytes
コンパイル時間 32,006 ms
実行使用メモリ 22,212 KB
スコア 147
最終ジャッジ日時 2018-05-26 00:01:46
ジャッジサーバーID
（参考情報） 		judge10 /
純コード判定しない問題か言語
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 924 ms
18,120 KB
testcase_01 AC 921 ms
22,196 KB
testcase_02 AC 921 ms
22,200 KB
testcase_03 AC 921 ms
22,196 KB
testcase_04 AC 920 ms
22,188 KB
testcase_05 AC 920 ms
22,200 KB
testcase_06 AC 923 ms
22,204 KB
testcase_07 AC 919 ms
22,192 KB
testcase_08 AC 921 ms
20,140 KB
testcase_09 AC 921 ms
20,152 KB
testcase_10 AC 920 ms
20,156 KB
testcase_11 AC 922 ms
22,192 KB
testcase_12 AC 924 ms
22,188 KB
testcase_13 AC 920 ms
18,132 KB
testcase_14 AC 922 ms
22,212 KB
testcase_15 AC 920 ms
22,200 KB
testcase_16 AC 921 ms
22,196 KB
testcase_17 AC 921 ms
20,156 KB
testcase_18 AC 923 ms
22,200 KB
testcase_19 AC 920 ms
22,188 KB
testcase_20 AC 921 ms
22,188 KB
testcase_21 AC 921 ms
22,192 KB
testcase_22 AC 920 ms
22,196 KB
testcase_23 AC 920 ms
22,200 KB
testcase_24 AC 920 ms
22,200 KB
testcase_25 AC 920 ms
20,152 KB
testcase_26 AC 920 ms
16,080 KB
testcase_27 AC 921 ms
22,192 KB
testcase_28 AC 922 ms
22,188 KB
testcase_29 AC 921 ms
22,192 KB
testcase_30 AC 918 ms
18,112 KB
testcase_31 AC 923 ms
22,204 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 2.3.1.61919 (57c81319)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

//#define DEBUG
//#undef DEBUG

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Text;
using System.Diagnostics;
#if DEBUG
using System.Threading;
#endif

public class StickXor{

#region field
	
	int N, K;
	int[][] A;
	int[] L;
#endregion
	
	void Solve(){
		var d = ria();
		N = d[0]; K = d[1];
		L = ria();
		A = new int[N][];
		for(int i=0;i<N;i++){
			A[i] = rs().Select(c => (int)(c - '0')).ToArray();
		}
		
		SA(900);
		var sb = new StringBuilder();
		for(int i=0;i<K;i++){
			if(maxD[i] == 0){
				sb.AppendLine(String.Format("{0} {1} {2} {3}", maxY[i] + 1, maxX[i] + 1, maxY[i] + 1 + L[i] - 1, maxX[i] + 1));
			} else {
				sb.AppendLine(String.Format("{0} {1} {2} {3}", maxY[i] + 1, maxX[i] + 1, maxY[i] + 1, maxX[i] + 1 + L[i] - 1));
			}
		}
		
		Console.Write(sb.ToString());
	}
	
	
	int maxSc = (int) -1e9;
	int[] maxY = null;
	int[] maxX = null;
	int[] maxD = null;
	
	bool UpdateMax(int[] ys, int[] xs, int[] ds, int sc, bool calc = false){
		//if(calc) sc = calcScoreNaive(ys, xs, ds);
		if(sc > maxSc){
//Err("update: minSc:{0} -> {1} : {2} [ms]",maxSc, sc, Now());
			maxSc = sc;
			maxY = (int[]) ys.Clone();
			maxX = (int[]) xs.Clone();
			maxD = (int[]) ds.Clone();
			return true;
		}
		return false;
	}
	
	
	void SA(long tlimit){
		long tstart = Now();
		long timeLimitDuration = tlimit - tstart;
		int[][] a = new int[N][];
		for(int i=0;i<N;i++){
			a[i] = new int[N];
			for(int j=0;j<N;j++){
				a[i][j] = A[i][j];
			}
		}
		
		var rnd = new Xor128(25252525);
		int[] xs = new int[K];
		int[] ys = new int[K];
		int[] ds = new int[K];
		for(int i=0;i<K;i++){
			xs[i] = rnd.Next(N - L[i] + 1);
			ys[i] = rnd.Next(N - L[i] + 1);
			ds[i] = rnd.Next(2);
		}
		for(int k=0;k<K;k++){
			var x = xs[k];
			var y = ys[k];
			if(ds[k] == 0){
				// vertical
				for(int i=y;i<y+L[k];i++) a[i][x] ^= 1;
			} else {
				// horizontal
				for(int j=x;j<x+L[k];j++) a[y][j] ^= 1;
			}
		}
		
		int sc = 0;
		for(int i=0;i<N;i++) for(int j=0;j<N;j++) sc += a[i][j];
		sc = N * N - sc;
		UpdateMax(ys, xs, ds, sc);
		
		long cnt = 0;
		long t1 = Now();
		
		while(true){
			cnt++;
			if(cnt % 100 == 0 && (t1 = Now()) - tstart > timeLimitDuration) break;
			var vh = rnd.Next(2);
			var pos = rnd.Next(K);
			var y = rnd.Next(N - L[pos] + 1);
			var x = rnd.Next(N - L[pos] + 1);
			
			int gain = 0;
			if(vh == 0){
				// vertical
				int one = 0;
				int zero = 0;
				for(int i=y;i<y+L[pos];i++) one += a[i][x];
				zero = L[pos] - one;
				gain = one - zero;
			} else {
				// horizontal
				int one = 0;
				int zero = 0;
				for(int j=x;j<x+L[pos];j++) one += a[y][j];
				zero = L[pos] - one;
				gain = one - zero;
			}
			
			var nsc = sc + gain;
			if(SAgain(nsc, sc, t1, tstart, timeLimitDuration)){
				sc = nsc;
				xs[pos] = x; ys[pos] = y; ds[pos] = vh;
				if(vh == 0){
					// vertical
					for(int i=y;i<y+L[pos];i++) a[i][x] ^= 1;
				} else {
					// horizontal
					for(int j=x;j<x+L[pos];j++) a[y][j] ^= 1;
				}
				UpdateMax(ys, xs, ds, sc);
			}
		}
		
//Err("cnt: {0}", cnt);
		
		
		
		
	}
#region del
	

#endregion
	
	
	
	
#region SA-Template
	

	static Xor128 lottery = new Xor128(25252525);
	const double C = 2800;
	
	static bool SAgain(double score, double prev, long now, long start, long limitDuration){
		if( score > prev ) return true;
		double ratio = - (prev - score) / prev;
		double remainingTime = (now - start) / (double) limitDuration;
		if( remainingTime > 1.0) return false;
		remainingTime = 1 - remainingTime;

		double acProb = Math.Exp(C * ratio / remainingTime);

		return (lottery.NextD() + Eps) < acProb ;
	}
	static bool MCgain(double score, double prev, long now, long start, long limitDuration){
		if( score > prev ) return true;
		return false;
	}
	static bool SAlose(double score, double prev, long now, long start, long limitDuration){
		if( score < prev ) return true;
		double ratio = (prev - score) / prev;
		double remainingTime = (now - start) / (double) limitDuration;
		if( remainingTime > 1.0) return false;
		remainingTime = 1 - remainingTime;

		double acProb = Math.Exp(C * ratio / remainingTime);

		return (lottery.Next(1000000) / 1000000.0 + Eps) < acProb ;
	}
	static bool MClose(double score, double prev, long now, long start, long limitDuration){
		if( score < prev ) return true;
		return false;
	}
	
#endregion
	
	
#region TimeCount
	
	static Stopwatch sw = new Stopwatch();
	static bool TU=false;
	static long TimeLimit=950;
	static bool TimeUp(){
		if(TU){return true;}
		return TU = (sw.ElapsedMilliseconds>TimeLimit);
	}
	static long Now(){return sw.ElapsedMilliseconds;}
	
	static bool TUT=false;
	static long TimeLimitT=3000000;
	static bool TimeUpT(){
		if(TUT){return true;}
		return TUT=(sw.ElapsedTicks>TimeLimitT);
	}
	static long NowT(){return sw.ElapsedTicks;}
	
	static void TimeStamp(String title){
		Console.Error.WriteLine("{0}:{1} [ms]",title,Now());
	}
#endregion
	
	
	
#region Decode 
	
	const int MD = 10;
	const int MASK = 0x2FF;
	static int decR(int s){return s >> MD;}
	static int decC(int s){return s & MASK;}
	static int enc(int r,int c){return (r << MD) + c;}
	static int[] dy=new int[]{0, -1,  0, 1, 1, -1, -1, 1};
	static int[] dx=new int[]{1,  0, -1, 0, 1, 1, -1, -1};
	const double Inf = 1e18;
	const double Eps = 1e-9;
	
	static int D2(int x0, int y0, int x1, int y1){
		x1 -= x0; y1 -= y0;	return x1 * x1 + y1 * y1;
	}
	static double D(int x0, int y0, int x1, int y1){
		return Math.Sqrt(D2(x0, y0, x1, y1));
	}
	
#endregion
	
	bool InRange(int t, int l, int r){ return l <= t && t < r;}
	void Swap<T> (ref T a, ref T b) { T t = a; a = b; b = t;}
	bool NextPermutation<T>(T[] a)where T:IComparable<T>{
		for(int i=a.Length-2;i>=0;i--){
			if(a[i].CompareTo(a[i+1])<0){
				int trgt=Array.FindLastIndex(a,x=>a[i].CompareTo(x)<0);
				Swap(ref a[i],ref a[trgt]);
				Array.Reverse(a,i+1,a.Length-(i+1));
				return true;
			}
		}
		Array.Reverse(a);
		return false;
	}
	
	static void Err(String format, params object[] args){
		Console.Error.WriteLine(format, args);
	}
	
	static int seed = 0;
	
	public static void Main(){
		//seed = int.Parse(args[0]);
		//C = double.Parse(args[1]);
		sw.Start();
		var sx = new StickXor();
		sx.Solve();
	}
	
	
	static String rs(){return Console.ReadLine();}
	static int ri(){return int.Parse(Console.ReadLine());}
	static long rl(){return long.Parse(Console.ReadLine());}
	static double rd(){return double.Parse(Console.ReadLine());}
	static String[] rsa(char sep=' '){return Console.ReadLine().Split(sep);}
	static int[] ria(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>int.Parse(e));}
	static long[] rla(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>long.Parse(e));}
	static double[] rda(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>double.Parse(e));}
	
}

#if DEBUG
static class DebugClass{
	
}
#endif


class Xor128{
	uint x = 123456789;
	uint y = 362436069;
	uint z = 521288629;
	uint w = 88675123; 
	
	const double div = 1.0 / 1048575.0;
	
	public Xor128(){
	}
	
	public Xor128(uint seed){
		z ^= seed;
	}
	
	public uint Next(){
		uint t = x ^ (x << 11);
		x = y; y = z; z = w;
		return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
	}
	public int Next(int ul){
		return ul == 0 ? 0 : NextI(0,ul-1);
	}
	public int NextI(int from,int to){
		int mod=to-from+1;
		int ret=(int)(Next()%mod);
		return ret+from;
	}
	
	public double NextD(){
		return (Next() & 1048575) * div;
	}
	
	
}
0