Submission #1312526

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312526		salmon	Light Bulbs (EGOI24_lightbulbs)	C++20	22 / 100	21 ms	448 KiB

Main

#include <bits/stdc++.h>
using namespace std;

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

int N;

bool ans[110][110];
bool ansh[110][110];
bool ansv[110][110];
int buf;
vector<int> h,v;
vector<pair<int,int>> hg;
vector<pair<int,int>> vg;
vector<pair<int,int>> chain;



void print(){
	printf("?\n");
	
	for(int i = 0; i < N; i++){
		for(int j = 0; j < N; j++) printf("%d",(int)ans[i][j]);
		printf("\n");
	}
	
	fflush(stdout);
}

int query(){
	print();
	
	int h;
	scanf(" %d",&h);
	
	return h;
}

void answer(){
	printf("!\n");
	
	for(int i = 0; i < N; i++){
		for(int j = 0; j < N; j++) printf("%d",(int)ans[i][j]);
		printf("\n");
	}
	
	fflush(stdout);
}

void remove(int x, int y, bool horz){
	if(horz) h.erase(find(h.begin(),h.end(),x));
	else v.erase(find(v.begin(),v.end(),y));
}

void load(int x, int y, bool horz){
	if(horz){
		ansh[x][y] = 1;
		hg.push_back({x,y});
		remove(x,y,horz);
	}
	else{
		ansv[x][y] = 1;
		vg.push_back({x,y});
		remove(x,y,horz);
	}
}

void reset(){
	for(int i = 0; i < N; i++){
		for(int j = 0; j < N; j++){
			ans[i][j] = 0;
		}
	}
}

bool check(int i, int j){
	if(ansh[0][0]){
		reset();
		
		ans[0][0] = 1;
		ans[i][j] = 1;
		
		if(query() % N == 0) return 1;
		return 0;
	}
	else{
		reset();
		
		ans[0][0] = 1;
		ans[i][j] = 1;
		
		if(query() % N == 0) return 0;
		return 1;
	}
}

pair<int,int> chair(int x1, int y1, int x2, int y2, int x3, int y3){
	reset();
	
	ans[x1][y1] = 1;
	ans[x2][y2] = 1;
	ans[x3][y3] = 1;
	
	if(hg.size() >= 2){
		ans[hg[0].first][hg[0].second] = 1;
		ans[hg[1].first][hg[1].second] = 1;
	}
	else{
		ans[vg[0].first][vg[0].second] = 1;
		ans[vg[1].first][vg[1].second] = 1;
	}
	
	pair<int,int> ii;
	int temp = query();
	
	if(temp == N * 5 - 4){
		ii = {2,1};
	}
	else if(temp == N * 5 - 6){
		ii = {1,2};
	}
	else if(temp == N * 4 - 3){
		ii = {1,1};
	}
	else if(temp == N * 4 - 4){
		ii = {0,2};
	}
	else if(temp == N * 4){
		ii = {2,0};
	}
	
	if(hg.size() < 2) swap(ii.first,ii.second);
	return ii;
}

void breakchain(bool horz){
	if(((chain[0].first == chain[1].first) + horz + chain.size() - 1) % 2 == 0){
		if(chain[0].first == chain[1].first){
			v.push_back(chain[0].second);
		}
		else{
			h.push_back(chain[0].first);
		}
	}
	else{
		int n = chain.size() - 1;
		
		if(chain[n].first == chain[n - 1].first){
			v.push_back(chain[n].second);
		}
		else{
			h.push_back(chain[n].first);
		}
	}
	
	while(!chain.empty()){
		if(chain.size() == 1){
			if(horz){
				v.push_back(chain[0].second);
			}
			else{
				v.push_back(chain[0].first);
			}
		}
	}
}

int main(){
	
	scanf(" %d",&N);
	
	for(int i = 0; i < N; i++){
		h.push_back(i);
		v.push_back(i);
	}
	
	for(int i = 0; i < N; i++){
		for(int j = 0; j < N; j++){
			ans[i][j] = false;
			ansh[i][j] = false;
			ansv[i][j] = false;
		}
	}
	
	
	for(int j = 0; j < N; j++){
		ans[0][j] = true; 
	}
	
	print();
	scanf(" %d",&buf);
	
	if(buf == N * N){
		answer();
		return 0;
	}
	
	int num1 = buf;
	
	ans[0][0] = false;
	
	print();
	scanf(" %d",&buf);
	
	if(buf % N == 0 && buf != N){
		load(0,0,true);
	}
	else{
		if(buf == num1){
			load(0,0,true);
		}
		else{
			load(0,0,false);
		}
	}
	
	while(!h.empty() && !v.empty() && chain.empty()){
		if(N < 40){
			load(h[0],v[0],check(h[0],v[0]));
			continue;
		}	
		
		
		if(N - h.size() < 2 && N - v.size() < 2){
			int x = h[rng() % h.size()];
			int y = v[rng() % v.size()];
			
			load(x,y,check(x,y));
			
			continue;
		}
		
		if(!chain.empty()){
			if(!h.empty() && !v.empty()){
				int n = chain.size() - 1;
				
				int x = h[rng() % h.size()];
				int y = v[rng() % v.size()];
				
				pair<int,int> ii;
				
				if(chain[n - 1].first == chain[n].first){
					ii = chair(chain[n].first,chain[n].second,x,chain[n].second,x,y);
				
					if(ii == make_pair(2,0)){
						breakchain(true);
						load(x,y,true);
					}
					else if(ii == make_pair(0,2)){
						breakchain(false);
						load(x,y,false);
					}
					else if(ii == make_pair(1,1)){
						breakchain(false);
						load(x,y,true);
					}	
					else if(ii == make_pair(2,1)){
						vector<pair<int,int>> temp = {{x,chain[n].second}, {x,y}};
						
						breakchain(true);
						chain = temp;
					}
					else if(ii == make_pair(1,2)){
						load(x,y,false);
						
						chain.push_back({x,chain[n].second});
					}
				}
				else{
					ii = chair(chain[n].first,chain[n].second,chain[n].first,y,x,y);
					
					if(ii == make_pair(2,0)){
						breakchain(true);
						load(x,y,true);
					}
					else if(ii == make_pair(0,2)){
						breakchain(false);
						load(x,y,false);
					}
					if(ii == make_pair(1,1)){
						breakchain(true);
						load(x,y,false);
					}	
					else if(ii == make_pair(1,2)){
						vector<pair<int,int>> temp = {{chain[n].first,y}, {x,y}};
						
						breakchain(false);
						chain = temp;
					}
					else if(ii == make_pair(2,1)){
						load(x,y,true);
						
						chain.push_back({chain[n].first,y});
					}
				}
			}
			else{
				int n = chain.size() - 1;
				
				breakchain(check(chain[n].first,chain[n].second));
			}
		}
		else{
			if(h.size() <= 2 || v.size() <= 2){
				if(h.size() <= 2){
					reset();
					
					ans[h[0]][v[0]] = 1;
					ans[h[0]][v[1]] = 1;
					
					if(query() == 2 * N){
						load(h[0],v[0],false);
						load(h[0],v[1],false);
					}
					else{
						if(check(h[0],v[0])){
							load(h[0],v[0],true);
						}
						else{
							load(h[0],v[1],true);
						}
					}
				}
				else{
					reset();
					
					ans[h[0]][v[0]] = 1;
					ans[h[1]][v[0]] = 1;
					
					if(query() == 2 * N){
						load(h[0],v[0],true);
						load(h[1],v[0],true);
					}
					else{
						if(!check(h[0],v[0])){
							load(h[0],v[0],false);
						}
						else{
							load(h[1],v[0],false);
						}
					}
				}
			}
			else{
				shuffle(h.begin(),h.end(),rng);
				shuffle(v.begin(),v.end(),rng);
				
				pair<int,int> ii = chair(h[0],v[0],h[0],v[1],h[1],v[1]);
				
				int h0 = h[0];
				int h1 = h[1];
				int v0 = v[0];
				int v1 = v[1];
				
				if(ii == make_pair(2,0)){
					load(h0,v0,true);
					load(h1,v1,true);
				}
				else if(ii == make_pair(0,2)){
					load(h0,v0,false);
					load(h1,v1,false);
				}
				else if(ii == make_pair(1,1)){
					load(h0,v0,true);
					load(h1,v1,false);
				}	
				else if(ii == make_pair(1,2)){
					load(h0,v0,false);
					
					vector<pair<int,int>> temp = {{h0,v1}, {h1,v1}};
					
					chain = temp;
				}
				else if(ii == make_pair(2,1)){
					load(h1,h1,true);
					
					vector<pair<int,int>> temp = {{h0,v0}, {h0,v1}};
					
					chain = temp;
				}
			}
		}
		
		
	}
	
	if(h.empty()){
		for(int i = 0; i < N; i++){
			for(int j = 0; j < N; j++){
				ans[i][j] = ansh[i][j];
			}
		}
	}
	else if(v.empty()){
		for(int i = 0; i < N; i++){
			for(int j = 0; j < N; j++){
				ans[i][j] = ansv[i][j];
			}
		}
	}
	
	answer();
}	

Compilation message (stderr)

Main.cpp: In function 'int query()':
Main.cpp:34:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |         scanf(" %d",&h);
      |         ~~~~~^~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:170:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  170 |         scanf(" %d",&N);
      |         ~~~~~^~~~~~~~~~
Main.cpp:191:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  191 |         scanf(" %d",&buf);
      |         ~~~~~^~~~~~~~~~~~
Main.cpp:203:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  203 |         scanf(" %d",&buf);
      |         ~~~~~^~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 0 / 78