#260715 (C++14) No.5002 stick xor

提出ソース

結果

問題	No.5002 stick xor
ユーザー	kuuso1
提出日時	2018-05-27 01:46:49
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	943 ms / 1,000 ms
コード長	7,142 bytes
コンパイル時間	35,724 ms
実行使用メモリ	1,800 KB
スコア	40,963
最終ジャッジ日時	2018-05-27 01:51:56
ジャッジサーバーID （参考情報）	judge6 /
	純コード判定しない問題か言語

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	940 ms 1,792 KB
testcase_01	AC	939 ms 1,796 KB
testcase_02	AC	940 ms 1,796 KB
testcase_03	AC	940 ms 1,796 KB
testcase_04	AC	940 ms 1,796 KB
testcase_05	AC	940 ms 1,744 KB
testcase_06	AC	942 ms 1,796 KB
testcase_07	AC	939 ms 1,744 KB
testcase_08	AC	939 ms 1,740 KB
testcase_09	AC	941 ms 1,740 KB
testcase_10	AC	939 ms 1,796 KB
testcase_11	AC	940 ms 1,748 KB
testcase_12	AC	941 ms 1,792 KB
testcase_13	AC	940 ms 1,748 KB
testcase_14	AC	941 ms 1,796 KB
testcase_15	AC	941 ms 1,796 KB
testcase_16	AC	940 ms 1,796 KB
testcase_17	AC	940 ms 1,796 KB
testcase_18	AC	940 ms 1,792 KB
testcase_19	AC	941 ms 1,796 KB
testcase_20	AC	940 ms 1,800 KB
testcase_21	AC	940 ms 1,792 KB
testcase_22	AC	940 ms 1,748 KB
testcase_23	AC	940 ms 1,748 KB
testcase_24	AC	939 ms 1,744 KB
testcase_25	AC	941 ms 1,744 KB
testcase_26	AC	940 ms 1,744 KB
testcase_27	AC	943 ms 1,744 KB
testcase_28	AC	941 ms 1,748 KB
testcase_29	AC	940 ms 1,792 KB
testcase_30	AC	940 ms 1,788 KB
testcase_31	AC	940 ms 1,744 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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 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(){
	
}


void OutputSolution(vector<int> res){
	for(int i=0;i<N;i++){
		cout << (i + 1) << " " << (res[i] + 1) << endl;
	}
}
	
// 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 aa[maxN][maxN];
int calcScoreNaive(int ys[], int xs[], int ds[]){
	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){
		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;
}


int a[maxN][maxN];
int xs[maxK];
int ys[maxK];
int ds[maxK];

void SA(ll tlimit){
	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(){
	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;
}

yukicoder

結果

テストケース

ソースコード