結果

問題 No.5002 stick xor
コンテスト
ユーザー kuuso1
提出日時 2018-05-27 03:23:18
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 941 ms / 1,000 ms
コード長 8,838 bytes
コンパイル時間 34,088 ms
実行使用メモリ 1,856 KB
スコア 40,971
最終ジャッジ日時 2018-05-27 03:23:53
ジャッジサーバーID
（参考情報） 		judge9 /
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <bits/stdc++.h>
#include <time.h>
#include <sys/timeb.h>
#include <cstdio>
#include <sys/time.h>

using namespace std;
#define ll long long
#define uint unsigned int
#define ulong unsigned long long int

#define maxN 200
#define maxK 600

int N, K;
int L[maxK];
int A[maxN][maxN];

int H, W;

class Acc2{
public:
	int H,W;
	int acc[maxN][maxN];
	int Calc(int x1,int y1,int x2,int y2){
		//return num of land [x1,x2)*[y1,y2); left-inclusive / right-noninclusive;
		if(x2 < x1 || y2 < y1) return 0;
		return acc[y2][x2] - acc[y2][x1] - acc[y1][x2] + acc[y1][x1];
	}
	
	Acc2(int a[maxN][maxN], int h, int w){
		Init(a, h, w);
	}
	Acc2(){
	}
	void Init(int M[maxN][maxN], int h, int w){
		H = h;
		W = w;
		for(int i=0;i<=H;i++){
			for(int j=0;j<=W;j++){
				acc[i][j] = (i == 0 || j == 0) ? 0 : M[i-1][j-1];
			}
		}
		
		for(int i=1;i<=H;i++){
			for(int j=1;j<=W;j++){
				acc[i][j] += acc[i][j-1];
			}
		}
		for(int j=1;j<=W;j++){
			for(int i=1;i<=H;i++){
				acc[i][j] += acc[i-1][j];
			}
		}
	}
};










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


class Timer{
public:
	Timer(){
		cycle_per_sec = (ulong) 2.7e9; 
	}
	void Start(){
		begin_cycle = getCycle();
	}
	double getTime(){
		return (double)(getCycle() - begin_cycle) / cycle_per_sec;
	}
	int elapsedMilliseconds(){
		return (int)( 1000 * getTime() );
	}

	ulong getCycle(){
		uint low, high;
		__asm__ volatile ("rdtsc" : "=a" (low), "=d" (high));
		return ((ulong) low) | ((ulong) high << 32);
	}
private:
	ulong begin_cycle;
	ulong cycle_per_sec;
};

Timer T;
ll Now(){return (ll) T.elapsedMilliseconds();}

const int MD = 10;
const int MASK = 0x3FF;
inline int decR(int s){return s >> MD;}
inline int decC(int s){return s & MASK;}
inline int enc(int r,int c){return (r << MD) + c;}
int dy[]{0, 1, 1, 1,  0, -1, -1, -1, 0,-2, 0,2};
int dx[]{1, 1, 0,-1, -1, -1,  0,  1, 2, 0,-2,0};
const double Inf = 1e18;
const double Eps = 1e-9;
bool InRange(int t, int l, int r){ return l <= t && t < r;}
void Swap(int &a, int &b){ int t = a; a = b; b = t;}

void Init(){
	
}

	
// SA template

	Xor128 lottery(25252525);
	const double C = 2400;
	const double invLimitDuration = 1 / 900.0;
	
	inline 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) * invLimitDuration;
		if( remainingTime > 1.0) return false;
		remainingTime = 1 - remainingTime;

		double acProb = exp(C * ratio / remainingTime);

		return (lottery.NextD() + Eps) < acProb ;
	}
	bool MCgain(double score, double prev, long now, long start, long limitDuration){
		if( score > prev ) return true;
		return false;
	}


int calcScoreNaive(int ys[], int xs[], int ds[]){
	int aa[maxN][maxN];
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
			aa[i][j] = A[i][j];
		}
	}
	for(int k=0;k<K;k++){
		int x = xs[k];
		int y = ys[k];
		if(ds[k] == 0){
			// vertical
			for(int i=y;i<y+L[k];i++) aa[i][x] ^= 1;
		} else {
			// horizontal
			for(int j=x;j<x+L[k];j++) aa[y][j] ^= 1;
		}
	}
	
	int sc = 0;
	for(int i=0;i<N;i++) for(int j=0;j<N;j++) sc += aa[i][j];
	sc = N * N - sc;
	return sc;
}







int maxSc = (int) -1e9;
int maxY[maxK];
int maxX[maxK];
int maxD[maxK];

bool UpdateMax(int ys[], int xs[], int ds[], int sc, bool calc = false){
	if(calc) sc = calcScoreNaive(ys, xs, ds);
	if(sc > maxSc){
//cerr << "update: maxSc:" << maxSc << " -> " << sc << " : " << Now() <<" [ms]" << endl;

		maxSc = sc;
		for(int i=0;i<K;i++){
			maxY[i] = ys[i];
			maxX[i] = xs[i];
			maxD[i] = ds[i];
		}
		return true;
	}
	return false;
}

void Greedy1(){
	
	vector<pair<int, int>> ls(K);
	for(int i=0;i<K;i++){
		ls[i] = make_pair(-L[i], i);
	}
	sort(ls.begin(), ls.end());
	
	int a[maxN][maxN];
	
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++) a[i][j] = A[i][j];
	}
	
	int xs[maxK];
	int ys[maxK];
	int ds[maxK];
	Acc2 sum2;
	
	for(int k=0;k<K;k++){
		int l = ls[k].first * -1;
		sum2.Init(a, N, N);
		int y = -1, x = -1, vh = -1;
		int max = -1;
		for(int i=0;i+l <= N;i++){
			for(int j=0;j<N;j++){
				int s = sum2.Calc(j, i, j + 1, i + l);
				if(s > max){
					max = s;
					x = j; y = i; vh = 0;
				}
			}
		}
		for(int i=0;i<N;i++){
			for(int j=0;j+l<=N;j++){
				int s = sum2.Calc(j, i, j + l, i + 1);
				if(s > max){
					max = s;
					x = j; y = i; vh = 1;
				}
			}
		}
		
		int idx = ls[k].second;
		xs[idx] = x;
		ys[idx] = y;
		ds[idx] = vh;
		
		
		if(vh == 0){
			for(int i=y;i<y+l;i++) a[i][x] ^= 1;
		} else {
			for(int j=x;j<x+l;j++) a[y][j] ^= 1;
		}
		
	}
	
	UpdateMax(ys, xs, ds, 0, true);
	
}


void SA(ll tlimit){
	int a[maxN][maxN];
	int xs[maxK];
	int ys[maxK];
	int ds[maxK];

	ll tstart = Now();
	ll timeLimitDuration = tlimit - tstart;
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
			a[i][j] = A[i][j];
		}
	}
	
	Xor128 rnd(25252525);
	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++){
		int x = xs[k];
		int 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 = calcScoreNaive(ys, xs, ds);
	UpdateMax(ys, xs, ds, sc);
	
	ll cnt = 0;
	ll t1 = Now();
	
	
	while(true){
		cnt++;
		if(cnt % 16384 == 0 && (t1 = Now()) - tstart > timeLimitDuration) break;
		int vh = rnd.Next(2);
		int pos = rnd.Next(K);
		int y = rnd.Next(vh == 0 ? N - L[pos] + 1 : N);
		int x = rnd.Next(vh == 1 ? N - L[pos] + 1 : N);
		
		int one = 0;
		int zero = 0;
		
		if(vh == 0){
			// vertical
			for(int i=y;i<y+L[pos];i++) one += a[i][x];
		} else {
			// horizontal
			for(int j=x;j<x+L[pos];j++) one += a[y][j];
		}
		if(ds[pos] == 0){
			// vertical
			for(int i=ys[pos];i<ys[pos]+L[pos];i++) one += a[i][xs[pos]];
		} else {
			// horizontal
			for(int j=xs[pos];j<xs[pos]+L[pos];j++) one += a[ys[pos]][j];
		}
			
		int tot = 2 * L[pos];
//Err("y:{0}, x:{1}, vh: {2}, ys[pos]:{3}, xs[pos]:{4}, ds[pos]:{5}, L[pos]:{6}",y, x, vh, ys[pos], xs[pos], ds[pos], L[pos]);
		if(vh == 0 && ds[pos] == 0){
			if(x == xs[pos]){
				if(y <= ys[pos] && ys[pos] <= y + L[pos] - 1){
					for(int i=ys[pos]; i <= y + L[pos] - 1; i++){
						one -= 2 * a[i][x];
						tot -= 2;
					}
				} else 	if(ys[pos] <= y && y <= ys[pos] + L[pos] - 1){
					for(int i=y; i <= ys[pos] + L[pos] - 1; i++){
						one -= 2 * a[i][x];
						tot -= 2;
					}
				}
			}
		}
		if(vh == 1 && ds[pos] == 1){
			if(y == ys[pos]){
				if(x <= xs[pos] && xs[pos] <= x + L[pos] - 1){
					for(int j=xs[pos]; j <= x + L[pos] - 1; j++){
						one -= 2 * a[y][j];
						tot -= 2;
					}
				} else if(xs[pos] <= x && x <= xs[pos] + L[pos] - 1){
					for(int j=x; j <= xs[pos] + L[pos] - 1; j++){
						one -= 2 * a[y][j];
						tot -= 2;
					}
				}
			}
		}
		if(vh == 0 && ds[pos] == 1){
			if(InRange(x, xs[pos], xs[pos] + L[pos]) && InRange(ys[pos], y, y + L[pos])){
				one -= 2 * a[ys[pos]][x];
				tot -= 2;
			}
		}
		if(vh == 1 && ds[pos] == 0){
			if(InRange(xs[pos], x, x + L[pos]) && InRange(y, ys[pos], ys[pos] + L[pos])){
				one -= 2 * a[y][xs[pos]];
				tot -= 2;
			}
		}
		
		zero = tot - one;
		
		int nsc = sc + (one - zero);
		if(SAgain(nsc, sc, t1, tstart, timeLimitDuration)){
			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;
			}
			if(ds[pos] == 0){
				// vertical
				for(int i=ys[pos];i<ys[pos]+L[pos];i++) a[i][xs[pos]] ^= 1;
			} else {
				// horizontal
				for(int j=xs[pos];j<xs[pos]+L[pos];j++) a[ys[pos]][j] ^= 1;
			}
			sc = nsc;
			xs[pos] = x; ys[pos] = y; ds[pos] = vh;
			UpdateMax(ys, xs, ds, sc);
		} else {
		}
	}
	
//Err("cnt: {0}", cnt);
//cerr << cnt << endl;
	
	
	
}


void Solve(){
	Greedy1();
	SA(900);
	
	for(int i=0;i<K;i++){
		if(maxD[i] == 0){
			printf("%d %d %d %d\n", maxY[i] + 1, maxX[i] + 1, maxY[i] + 1 + L[i] - 1, maxX[i] + 1);
		} else {
			printf("%d %d %d %d\n", maxY[i] + 1, maxX[i] + 1, maxY[i] + 1, maxX[i] + 1 + L[i] - 1);
		}
	}
	
}



int main(){
	T.Start();
	cin >> N >> K;
	for(int i=0;i<K;i++){
		cin >> L[i];
	}
	
	string s;
	for(int i=0;i<N;i++){
		cin >> s;
		for(int j=0;j<N;j++){
			A[i][j] = (int) (s[j] - '0');
		}
	}

	Solve();


	return 0;
}
0