結果

問題 No.5002 stick xor
ユーザー IL_mstaIL_msta
提出日時 2018-05-26 00:13:03
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 988 ms / 1,000 ms
コード長 18,602 bytes
コンパイル時間 35,932 ms
実行使用メモリ 1,604 KB
スコア 31,457
最終ジャッジ日時 2018-05-26 00:14:13
ジャッジサーバーID
（参考情報） 		judge9 /
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 980 ms
1,604 KB
testcase_01 AC 976 ms
1,604 KB
testcase_02 AC 974 ms
1,600 KB
testcase_03 AC 981 ms
1,600 KB
testcase_04 AC 982 ms
1,600 KB
testcase_05 AC 973 ms
1,600 KB
testcase_06 AC 985 ms
1,604 KB
testcase_07 AC 980 ms
1,604 KB
testcase_08 AC 971 ms
1,600 KB
testcase_09 AC 975 ms
1,600 KB
testcase_10 AC 976 ms
1,604 KB
testcase_11 AC 976 ms
1,600 KB
testcase_12 AC 974 ms
1,604 KB
testcase_13 AC 976 ms
1,604 KB
testcase_14 AC 980 ms
1,604 KB
testcase_15 AC 987 ms
1,604 KB
testcase_16 AC 983 ms
1,600 KB
testcase_17 AC 977 ms
1,604 KB
testcase_18 AC 982 ms
1,600 KB
testcase_19 AC 976 ms
1,600 KB
testcase_20 AC 986 ms
1,600 KB
testcase_21 AC 974 ms
1,600 KB
testcase_22 AC 988 ms
1,604 KB
testcase_23 AC 979 ms
1,604 KB
testcase_24 AC 981 ms
1,600 KB
testcase_25 AC 980 ms
1,604 KB
testcase_26 AC 981 ms
1,600 KB
testcase_27 AC 979 ms
1,604 KB
testcase_28 AC 977 ms
1,600 KB
testcase_29 AC 975 ms
1,604 KB
testcase_30 AC 977 ms
1,600 KB
testcase_31 AC 976 ms
1,604 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define _USE_MATH_DEFINES
#pragma region include
#include <iostream>
#include <iomanip>
#include <stdio.h>

#include <sstream>
#include <algorithm>
#include <iterator>
#include <cmath>
#include <complex>

#include <string>
#include <cstring>
#include <vector>
#include <bitset>

#include <queue>
#include <set>
#include <map>
#include <stack>
#include <list>

#include <ctime>
////
//#include <random>//
#pragma endregion //#include
/////////

#pragma region typedef
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
#pragma endregion //typedef
////定数
const int INF = (int)1e9;
const LL MOD = (LL)1e9+7;
const LL LINF = (LL)4e18+20;
const LD PI = acos(-1.0);
const double EPS = 1e-9;
/////////
using namespace::std;
/////////
#pragma region Math
#pragma region
long long ext_gcd(long long a,long long b,long long& x,long long& y){
	if(b==0){
		x=1;y=0;return a;
	}
	long long q = a/b;
	long long g = ext_gcd(b,a-q*b,x,y);
	x = x - q*y;
	swap(x,y);
	return g;
}
template<class T>
inline T gcd(T a, T b){return b ? gcd(b, a % b) : a;}

#pragma endregion // 最大公約数 gcd
#pragma region
template<class T>
inline T lcm(T a, T b){return a / gcd(a, b) * b;}
#pragma endregion // 最小公倍数 lcm
#pragma region
long long invMod(long long a,long long m=MOD){
	long long x,y;
	ext_gcd(a,m,x,y);
	x %= m;
	if(x<0) x += m;
	return x;
}

/*
LL powMod(LL x,LL e,LL mod=MOD){
	LL prod = 1%mod;
	for(int i=63;i>=0;--i){
		prod = prod*prod % mod;
		if(e&1LL<<i)prod=prod*x%mod;
	}
	return prod;
}*/

LL powMod(LL num,LL n,LL mod=(LL)MOD){//(num**n)%mod
	num %= mod;//
	if( n == 0 ){
		return (LL)1;
	}
	LL mul = num;
	LL ans = (LL)1;
	while(n){
		if( n&1 ){
			ans = (ans*mul)%mod;
		}
		mul = (mul*mul)%mod;
		n >>= 1;
	}
	return ans;
}
/*
LL mod_inverse(LL num,LL mod=MOD){
	return powMod(num,MOD-2,MOD);
}*/
#pragma endregion //繰り返し二乗法 powMod
#pragma region
template<class T>
vector<T> getDivisor(T n){
	vector<T> v;
	for(int i=1;i*i<=n;++i){
		if( n%i == 0 ){
			v.push_back(i);
			if( i != n/i ){//平方数で重複して数えないように
				v.push_back(n/i);
			}
		}
	}
	sort(v.begin(), v.end());
	return v;
}
#pragma endregion //約数列挙 getDivisor(n):O(√n)
#pragma endregion //math
//Utility:便利な奴
#pragma region
template<class T>
void UNIQUE(vector<T>& vec){
	sort(vec.begin(),vec.end());
	vec.erase(unique(vec.begin(),vec.end()),vec.end() );
}
#pragma endregion // sort erase unique
////////////////////////////////
#pragma region 
long long  bitcount64(long long bits)
{
    bits = (bits & 0x5555555555555555) + (bits >> 1 & 0x5555555555555555);
    bits = (bits & 0x3333333333333333) + (bits >> 2 & 0x3333333333333333);
    bits = (bits & 0x0f0f0f0f0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f0f0f0f0f);
    bits = (bits & 0x00ff00ff00ff00ff) + (bits >> 8 & 0x00ff00ff00ff00ff);
    bits = (bits & 0x0000ffff0000ffff) + (bits >>16 & 0x0000ffff0000ffff);
    return (bits & 0x00000000ffffffff) + (bits >>32 & 0x00000000ffffffff);
}
#pragma endregion //その他
////////////////////////////////
struct edge_base{int to;LL cost;};
edge_base make_edge_base(int to,LL cost){
	edge_base ret = {to,cost};
	return ret;
}
#pragma region GRL
#pragma region //グラフ
template<class T,class EDGE>
void dijkstra(int root,int V,vector<T>& dist,vector<int>& prev,
	vector< vector<EDGE> > G	){
	priority_queue<pair<T,int>,vector<pair<T,int> >,greater<pair<T,int> > > que;
	
	dist.assign(V,LINF);
	prev.assign(V,-1);

	dist[root] = 0;
	que.push(pair<T,int>(0,root));//距離、頂点番号

	while( !que.empty() ){
		pair<T,int> p = que.top();que.pop();
		int v = p.second;
		if( dist[v] < p.first ) continue;
		for(int i=0;i < (int)G[v].size();++i){
			EDGE e = G[v][i];
			if( dist[e.to] > dist[v] + e.cost ){
				dist[e.to] = dist[v] + e.cost;
				prev[e.to] = v;
				que.push(pair<T,int>(dist[e.to],e.to));
			}
		}
	}
}
//経路復元,dijkstraにprev入れた
//http://ronly.hatenablog.com/entry/2017/06/17/161641
vector<int> get_path(vector<int>& prev,int t){
	vector<int> path;
	while(t!=-1){
		path.push_back( t );
		t = prev[t];
	}
	reverse(path.begin(),path.end());
	return path;
}
#pragma endregion //ダイクストラ法:O(|E|log|V|)
#pragma region //グラフ
void warshall_floyd(vector<vector<LL> >& dist,int V,const LL inf=LINF){
	for(int k=0;k<V;++k){
		for(int i=0;i<V;++i){
			if( dist[i][k] >= inf ) continue;
			for(int j=0;j<V;++j){
				if( dist[k][j] >= inf )continue;
				dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]);
			}
		}
	}
}
#pragma endregion //ワーシャルフロイド:O(|V|**3)
#pragma region
namespace FLOW{
//vector< vector<FLOW:edge> > G;

struct edge_flow : public edge_base{
	LL cap;//LD cap;//
	int rev;
};
edge_flow make_edge_flow(int to,LL cap,int rev,LL cost=1){
//edge_flow make_edge_flow(int to,LD cap,int rev,LL cost=1){
	edge_flow ret;
	
	ret.to = to;
	ret.cost = cost;
	ret.cap = cap;
	ret.rev = rev;
	return ret;
}

//*
class Graph{
public:
	int V;
	vector< vector<FLOW::edge_flow> > G;
	vector< LL > dist;
	vector< int > iter;
	vector< bool > used;
	void init(int v){
		V = v;
		G.resize(V);
	}
	void reset(){
		iter.assign(V,0);
		used.assign(V,false);
	}
	//directed graph
	void add_edge(int from,int to,LL cap){
		G[from].push_back( FLOW::make_edge_flow(to,cap,G[to].size()) );
		G[to].push_back( FLOW::make_edge_flow(from,0,G[from].size()-1) );
	}
	
private:
	//sから最短距離をBFSで計算する
	void bfs(int s){//許容量もチェックしている
		queue<int> que;
		dist = vector<LL>(V,-1);
		dist[s] = 0;
		que.push(s);
		while(!que.empty()){
			int v = que.front();que.pop();
			for(int i=0;i<(int)G[v].size();++i){
				edge_flow &e = G[v][i];
				if( e.cap > 0 && dist[e.to] < 0 ){
					dist[e.to] = dist[v] + 1;
					que.push(e.to);
				}
			}
		}
	}
private:
	//増加パスをDFSで探す
	LL dfs(int v,int t,LL f){
		if( v==t ) return f;
		for(int &i = iter[v];i<(int)G[v].size();++i){//?
			FLOW::edge_flow &e = G[v][i];
			if( e.cap>0 && dist[v] < dist[e.to]){
				LL d = this->dfs(e.to, t, min(f,e.cap) );
				if( d > 0){
					e.cap -= d;
					G[e.to][e.rev].cap += d;
					return d;
				}
			}
		}
		return 0;
	}
public:
	//sからtへの最大流量を求める
	LL max_flow(int s,int t){
		LL flow = 0;
		for(;;){
			this->bfs(s);
			if( dist[t] < 0 ) return flow;
			iter = vector<int>(V,0);
			LL f = this->dfs(s,t,LINF);
			do{
				flow += f;
				f = this->dfs(s,t,LINF);
			}while( f > 0 );
		}
	}
};
//*/
}
#pragma endregion //dinic :O(|E||V|^2)
#pragma region //グラフ
bool is_bipartite(int v,int c,vector< vector<int> >& G,vector<int>& Color){
	Color[v] = c;
	for(int i=0;i < (int)G[v].size();++i){//隣接グラフ
		if(Color[ G[v][i] ] == c ) return false;
		if(Color[ G[v][i] ] == 0 && 
			!is_bipartite(G[v][i],-c,G,Color)
			){
				return false;
		}
	}
	return true;
}
bool is_bipartite(int Root,vector< vector<int> >& Graph){
	int GraphSize = Graph.size();
	vector<int> Color(GraphSize,0);
	const int ColorNo = 1;
	return is_bipartite(Root,ColorNo,Graph,Color);
}
#pragma endregion //二部グラフチェック is_bipartite(root,GraphList)
#pragma region
namespace matching{
//https://beta.atcoder.jp/contests/soundhound2018/tasks/soundhound2018_c
int V;		//頂点数
vector< vector<int> > G;//グラフ
vector<int> match;//match[i]:頂点[i]がどことマッチされているか
vector<bool > used;//
void add_edge(int u,int v){
	G[u].push_back(v);
	G[v].push_back(u);
}
 
bool dfs(int v){
	/*
	https://mathtrain.jp/bipartitematching
	未マッチ辺・マッチ辺・未マッチ辺
	これを
	マッチ辺・未マッチ辺・マッチ辺
	に変えると
	1マッチが2マッチになる。
	未[済未]
	増加路を求めている。
	*/
	used[v] = true;//dfsのroot前に初期化される
	int size = G[v].size();
	for(int i=0;i<size;++i){
		int u = G[v][i];//
		int w = match[u];//
		if( w<0 || ((used[w]==false) && dfs(w)) ){
			/*
			マッチングされていない||
			使われてない&&
			*/
			match[v] = u;
			match[u] = v;
			return true;
		}
	}
	return false;
}
 
int bipartite_matching(){
	int res = 0;
	match = vector<int>(V,-1);//未マッチ状態に初期化
	for(int v=0;v<V;++v){
		if( match[v] < 0 ){
			used = vector<bool>(V,false);
			if( dfs(v) ){
				++res;
			}
		}
	}
	return res;
}
}
#pragma endregion //二部グラフの最大マッチング bipartite_matching()
#pragma endregion //
#pragma region 
vector< vector<LL> > NCK;//初期値:0
//http://sugarknri.hatenablog.com/entry/2016/07/16/165715
void makeinv(vector<LL>& inv,const LL P){
	int i;
	//const int varMAX = max(100000,(int)inv.size());
	const int varMAX = max(300010,(int)inv.size());
	
	inv = vector<LL>( varMAX+1,0);
	inv[1]=1;
	for(i=2;i<=varMAX;i++){
		inv[i] = (inv[P%i] * (P-P/i)%P ) % P;//OVF
		//inv[i] = powMod(i,P-2,P);
	}
}

LL nCk(LL N,LL k,LL mod = MOD){
	static vector<LL> inv;//modの逆元
	if( inv.size() == 0 ){
		makeinv(inv,mod);//modは素数を入れる
	}
	k = min(k,N-k);
	if( k < 0 || k > N){return 0;}
	if( k == 0 ){return 1;}
	if( k == 1 ){return N%mod;}
	LL ret = 1;
	for(int i=1;i<=k;++i){
		ret = (ret * ((N+1-i)%mod) )%mod;//ret*N:OVF
		ret = (ret * inv[i] )%mod;
	}
	return ret;
}
LL nCk_once(LL N,LL k,LL mod = MOD){//modは素数
	k = min(k,N-k);
	if( k < 0 || k > N ){return 0;}
	if( k == 0 ){return 1;}
	if( k == 1 ){return N%mod;}
	LL ret = 1;
	LL A=1;
	for(LL i=0;i<k;++i){
		A = (A * ((N-i)%mod) ) % mod;
	}
	LL B=1;
	for(LL i=2;i<=k;++i){
		B = (B * (i%mod) ) % mod;
	}
	ret = ( A * powMod(B,mod-2,mod) ) % mod;
	return ret;
}
#pragma endregion //組み合わせnCk(,10^5)
#pragma region
LL nCk_base(int N,int K,LL mod=MOD){
	if( K<0 || N < K ) return 0;//多く取り過ぎ
	K = min(K,N-K);
	if( K==0 ){return 1%mod;}
	if( K==1 ){return N%mod;}//%MOD;
	if( N<=10000 && NCK[N][K] ){
		return NCK[N][K];
	}
	//N個目を使わない:nCk(N-1,k)
	//N個目を使う	:nCk(N-1,k-1)
	LL ans = (nCk_base(N-1,K)+nCk_base(N-1,K-1) )%mod;//%MOD;
	if( N<=10000 ){
		NCK[N][K] = ans;
	}
	return ans;
}

#pragma endregion //組み合わせ メモ?

#pragma region DSL
class UnionFind{
public:
	int cNum;//要素数
	vector<int> parent;
	vector<int> count;
	vector< vector<int> > GList;
	UnionFind(int n){
		cNum = n;
		parent = vector<int>(n);
		count = vector<int>(n,1);
		GList.resize(n);
		for(int i=0;i<n;++i){
			parent[i] = i;
			GList[i].push_back(i);
		}
	}
	int find(int x){
		if( parent[x] == x ){return x;}
		return parent[x] = find( parent[x] );
	}
	bool same(int x,int y){return find(x) == find(y);}
	int Count(int x){return count[find(x)];}
	void add(int x,int y){//union
		x = find(x);
		y = find(y);
		if( x==y )return;
		parent[x] = y;
		
		count[y] += count[x];
		if( GList[y].size() < GList[x].size() ){
			swap(GList[x],GList[y]);
		}
		GList[y].insert( GList[y].end(),
			GList[x].begin(),GList[x].end() );
	}
};
#pragma endregion //UnionFind
#pragma region DSL
class BITree{//1-index
	int N;
	vector<LL> bit;
public:
	BITree(int n){
		N = n;
		bit = vector<LL>(N+1,0);//1-index
	}
	void add(int a,LL w){//aにwを足す
		if( a <= 0 || N < a) return;//a:[1,N]
		for(int i=a;i<=N;i += i & -i){
			bit[i] += w;
		}
	}
	LL sum(int a){//[1,a]の和,a:[1,N]
		/*
		1番目からa番目までの和、1-index
		*/
		LL ret = 0;
		if( a > N ) a = N;
		for(int i=a; i > 0; i -= i & -i){
			ret += bit[i];
		}
		return ret;
	}
};
#pragma endregion //BIndexTree
#pragma region
template <typename T>
class segmentTree{
	int N;//要素数
	vector< T > dat1;
	T VAL_E;//初期値
	T VAL_NULL;//空の値
public:
	segmentTree(){};
	/*segmentTree(int n,T val_E ):N(n),VAL_E(val_E){
		dat1.resize(2*n);
		dat1.assign(2*n,val_E);//初期化
	}*/
	void init(int n,T val_E,T val_N){
		N = n;
		VAL_E = val_E;
		VAL_NULL = val_N;
		int size = 2;
		while(size<N){
			size <<= 1;
		}
		N = size;
		dat1.resize(2*N);
		dat1.assign(2*N,val_E);
	}
	T SELECT(T L,T R){//扱う演算子
		T ans;
		ans = max(L,R);//
		return ans;
	}

	//index番目の値をvalに変更,indexは"0-index"
	void update(int i,T val){
		i += N-1;
		dat1[i] = val;
		while(i>0){
			i = (i-1)/2;
			dat1[i] = SELECT(dat1[i*2+1],dat1[i*2+2]);
		}
	}

	//区間[L,R)のSELECT
	/*
	調べている範囲[a,b),階数k,見る場所[L,R)
	*/
	T query(int a,int b,int k,int L,int R){
		if( R<=a || b<=L ){
			return VAL_E;//交差しない
		}
		if( a<=L && R<=b && dat1[k] != VAL_NULL ){
			return dat1[k];
		}

		T res = VAL_E;
		int mid = (L+R)/2;
		if( a < mid ) res = SELECT(res,query(a,b,k*2+1,L,mid) );
		if( mid < b ) res = SELECT(res,query(a,b,k*2+2,mid,R) );
		return res;
	}
	T query(int L,int R){
		return query(L,R,0,0,N);
	}
};
#pragma endregion //segment_tree

#pragma region 
//行列の積
namespace mymat{
	LL matMOD = MOD;//初期値10^9 + 7
};
template<class T>
vector< vector<T> > operator*( vector<vector<T> >& A,vector< vector<T> >& B){
	LL mod = mymat::matMOD;
	int R = A.size();
	int cen = A[0].size();
	int C = B[0].size();
	vector< vector<T> > ans(R,vector<T>(C,0) );
	for(int row=0;row<R;++row){
		for(int col=0;col<C;++col){
			for(int inner=0;inner< cen;++inner){
				/*ans[row][col] = (ans[row][col] + A[row][inner]*B[inner][col])%mod;
				//ans[row][col] = (ans[row][col] + A[row][inner]*B[inner][col]);
				ans[row][col] = (ans[row][col] + mod) % mod;
				//負になるときの処理
				*/
				ans[row][col] = (ans[row][col] + A[row][inner]*B[inner][col])%mod;
			}
		}
	}
	return ans;
}

template<class T>
vector< vector<T> > powMod(const vector< vector<T> >& mat,LL N,LL mod=MOD){
	mymat::matMOD = mod;
	int R = mat.size();
	int C = mat[0].size();
	//R==C
	vector< vector<T> > I(R,vector<T>(C,0));//単位元
	for(int i=0;i<R && i<C;++i){
		I[i][i] = 1;
	}
	if( N == 0 ){
		return I;
	}
	vector< vector<T> > mul(R,vector<T>(C)),ans(R,vector<T>(C));
	ans = I;
	mul = mat;
	while(N){
		if( N & 1 ){
			ans = ans*mul;
		}
		N >>= 1;
		mul = mul*mul;
	}
	return ans;
}
#pragma endregion //行列

#pragma region
#include<time.h>
namespace TIME{

clock_t start,end;
void time_start(){
	start = clock();
}
void time_set(int t){
	end = start + t;
}
bool check(){
	return clock() < end;
}

/*
unsigned long long get_cycle(){
	return __rdtsc();
}
unsigned long long start,limit;
void time_start(){
	start = get_cycle();
}
//あたいをーさぐらないとーだめー
void time_set(unsigned long long num){limit = num;}
bool check(){return (get_cycle() < start+limit);}
*/
}
#pragma endregion //時間計測

#pragma region

namespace RAND{
unsigned long xor128(){ 
	static unsigned long x=123456789,y=362436069,z=521288629,w=88675123; 
	unsigned long t; 
	t=(x^(x<<11));x=y;y=z;z=w;
	return( w=(w^(w>>19))^(t^(t>>8)) ); 
}
LL getRAND(LL P){
	return ((xor128()%P)+P)%P;
}
}

#pragma endregion //乱数

#pragma region
#pragma endregion //
////////////////////////
const int H = 60;
const int W = 60;
const int K = 500;
vector<int> L;
int start_score;//初期の白

class FLD{
	vector<vector<bool> > dat;
public:
	FLD(){
		dat = vector<vector<bool> >(H,vector<bool>(W,false));
	}
	void set (int r,int c,int color){
		dat[r][c] = color?true:false;
	}
	int cal(){//
		int ret = H*W;
		for(int r=0;r<H;++r){
			for(int c=0;c<W;++c){
				ret -= dat[r][c];
			}
		}
		return ret;
	}
	
	//操作後の点数-操作前の点数
	int cal_one(int r0,int c0,int r1,int c1){
		int ret = 0;
		int Len =abs(r1-r0) + abs(c1-c0) + 1;//長さ
		for(int r=r0;r<=r1;++r){
			for(int c=c0;c<=c1;++c){
				ret += dat[r][c];
			}
		}
		/*
		前　黒ret	白(Len-ret)
		後	黒(Len-ret)	白ret
		*/
		return ret - (Len-ret);
	}

	//UN_MOVE:MOVEと同じ操作を与える
	void MOVE(vector<int>& r0,vector<int>& c0,
			vector<int>& r1,vector<int>& c1){
		for(int i=0;i<K;++i){
			for(int r=r0[i];r<=r1[i];++r){
				for(int c=c0[i];c<=c1[i];++c){
					dat[r][c] = dat[r][c]?false:true;//反転
				}
			}
		}
	}

	//ひとつだけ操作する
	void MOVE_one(int r0,int c0,int r1,int c1){
		for(int r=r0;r<=r1;++r){
			for(int c=c0;c<=c1;++c){
				dat[r][c] = dat[r][c]?false:true;//反転
			}
		}
	}
};
//乱数で操作をセット
void setRAND(vector<int>& r0,vector<int>& c0,
			vector<int>& r1,vector<int>& c1){
	for(int i=0;i<K;++i){//K回操作する
		if( RAND::getRAND(2) ){
			//縦
			int r = (int)RAND::getRAND(H-L[i]+1);
			int c = (int)RAND::getRAND(W);
			r0[i] = r;
			r1[i] = r+L[i]-1;
			c0[i] = c;
			c1[i] = c;
		}else{
			//横
			int r = (int)RAND::getRAND(H);
			int c = (int)RAND::getRAND(W-L[i]+1);
			r0[i] = r;
			r1[i] = r;
			c0[i] = c;
			c1[i] = c + L[i]-1;
		}
	}
}

void solve(){
	TIME::time_start();
	int N,kk;
	cin>>N>>kk;//定数
	L = vector<int>(K);
	for(int i=0;i<K;++i){
		cin >> L[i];
	}
	FLD fld;
	
	for(int r=0;r<H;++r){
		string str;
		cin>>str;
		for(int c=0;c<W;++c){
			fld.set(r,c,str[c]-'0');
		}
	}
	start_score = fld.cal();//初期値

	//操作データK個
	vector<int> r0(K),r1(K),c0(K),c1(K);//0-index
	vector<int> best_r0(K),best_r1(K),best_c0(K),best_c1(K);//0-index
	
	setRAND(r0,c0,r1,c1);//操作列を得る
	fld.MOVE(r0,c0,r1,c1);//操作する
	int ANS = fld.cal() ;//スコアを計算
	int NOW_score = ANS;//現在のスコア
	best_r0 = r0;//最高得点の操作をコピー
	best_c0 = c0;
	best_r1 = r1;
	best_c1 = c1;
	
	TIME::time_set(970000);
	while( TIME::check() ){
		int ter = (int)RAND::getRAND(K);//ひとつ選ぶ
		int rr0,cc0,rr1,cc1;
		if( RAND::getRAND(2) ){
			//縦
			int r = (int)RAND::getRAND(H-L[ter]+1);
			int c = (int)RAND::getRAND(W);
			rr0 = r;
			cc0 = c;
			rr1 = r+L[ter]-1;
			cc1 = c;
		}else{
			//横
			int r = (int)RAND::getRAND(H);
			int c = (int)RAND::getRAND(W-L[ter]+1);
			rr0 = r;
			cc0 = c;
			rr1 = r;
			cc1 = c + L[ter]-1;
		}
		/////
		//操作の位置が重なる
		fld.MOVE_one(r0[ter],c0[ter],r1[ter],c1[ter]);//戻す
		fld.MOVE_one(rr0,cc0,rr1,cc1);//
		int res = fld.cal();

		if( res >= ANS ){
			r0[ter] = rr0;
			r1[ter] = rr1;
			c0[ter] = cc0;
			c1[ter] = cc1;
			
			{
				best_r0 = r0;
				best_r1 = r1;
				best_c0 = c0;
				best_c1 = c1;
				ANS = res;
			}
		}else{
			fld.MOVE_one(rr0,cc0,rr1,cc1);//
			fld.MOVE_one(r0[ter],c0[ter],r1[ter],c1[ter]);//戻す
		}
	}

	////////////////
	//出力
	for(int i=0;i<K;++i){
		cout <<best_r0[i]+1 << ' '
			<< best_c0[i]+1 << ' '
			<< best_r1[i]+1 << ' '
			<< best_c1[i]+1 << '\n';
	}
	cout << flush;
	cerr << "ANS:"<< ANS -start_score<< endl;
	cerr << "cal:"<< fld.cal() -start_score<< endl;
}

#pragma region main
signed main(void){
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	std::cout << std::fixed;//小数を10進数表示
	cout << setprecision(16);//小数点以下の桁数を指定//coutとcerrで別	

	solve();
}
#pragma endregion //main()
0