Submission #1315346

#	Time	Username	Problem	Language	Result	Execution time	Memory
1315346		salmon	Light Bulbs (EGOI24_lightbulbs)	C++20	96.70 / 100	37 ms	456 KiB

Main

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

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

#define mp(x,y) make_pair(x,y)

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;
bool bug = false;
int debug[110][110];

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 debugnum(){
	int numx = 0;
	int numy = 0;
	
	for(int i = 0; i < N; i++){
		bool is = false;
		for(int j = 0; j < N; j++){
			if(debug[i][j] && ans[i][j]) is = true;
		}
		numx += is;
	}
	
	for(int j = 0; j < N; j++){
		bool is = false;
		for(int i = 0; i < N; i++){
				if(!debug[i][j] && ans[i][j]) is = true;
		}
		numy += is;
	}
	printf("%d %d\n",v.size(),h.size());
	for(int i = 0; i < N; i++){
		for(int j = 0; j < N; j++){
			if(!ans[i][j]) printf("#");
			else printf("%d",debug[i][j]);
		}
		printf("\n");
	}
	
	return N *(numx + numy) - numx * numy;
}

int query(){
	print();
	
	int h;
	if(!bug) scanf(" %d",&h);
	
	if(bug) return debugnum();

	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){ if(find(h.begin(),h.end(),x) != h.end()) h.erase(find(h.begin(),h.end(),x)); }
	else{ if(find(v.begin(),v.end(),y) != v.end()) 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()){
		load(chain.back().first,chain.back().second,horz);
		horz = !horz;
		chain.pop_back();
	}
}

int main(){scanf(" %d",&N);
	//while(true){
	
	
	//
	if(bug){
		for(int i = 0; i < N; i++){
			for(int j = 0; j < N; j++){
				debug[i][j] = rng() % 2;
				printf("%d ",debug[i][j]);
			}
			printf("\n");
		}
	}
	//
	
	v.clear();
	h.clear();
	vg.clear();
	hg.clear();
	chain.clear();
	
	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; 
	}
	

	buf = query();

	if(buf == N * N){
		answer();
		return 0;
	}
	
	int num1 = buf;
	
	ans[0][0] = false;
	
	buf = query();
	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 < 10 || (v.size() == 1 && h.size() == 1 && chain.empty()) ){
			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 == mp(2,0)){
						breakchain(true);
						load(x,y,true);
					}
					else if(ii == mp(0,2)){
						breakchain(false);
						load(x,y,false);
					}
					else if(ii == mp(1,1)){
						breakchain(false);
						load(x,y,true);
					}	
					else if(ii == mp(2,1)){
						vector<pair<int,int>> temp = {{x,chain[n].second}, {x,y}};
						
						int temp1 = chain[n].second;
						
						breakchain(true);
						chain = temp;
						
						remove(x,temp1,true);
						remove(x,temp1,false);
						remove(x,y,false);
					}
					else if(ii == make_pair(1,2)){
						load(x,y,false);
						
						chain.push_back({x,chain[n].second});
						
						remove(x,chain[n].second,true);
					}
				}
				else{
					ii = chair(chain[n].first,chain[n].second,chain[n].first,y,x,y);
					
					if(ii == mp(2,0)){
						breakchain(true);
						load(x,y,true);
					}
					else if(ii == mp(0,2)){
						breakchain(false);
						load(x,y,false);
					}
					if(ii == mp(1,1)){
						breakchain(true);
						load(x,y,false);
					}	
					else if(ii == mp(1,2)){
						vector<pair<int,int>> temp = {{chain[n].first,y}, {x,y}};
						
						int temp1 = chain[n].first;
						
						breakchain(false);
						chain = temp;
						
						remove(temp1,y,true);
						remove(temp1,y,false);
						remove(x,y,true);
					}
					else if(ii == mp(2,1)){
						load(x,y,true);
						
						chain.push_back({chain[n].first,y});
						
						remove(chain[n].first,y,false);
					}
				}
			}
			else{
				int n = chain.size() - 1;
				
				breakchain(check(chain[n].first,chain[n].second));
			}
		}
		else{
			if(h.size() <= 2 || v.size() <= 2){
				if(v.size() >= 2 && h.size() <= 2){
					reset();
					
					int h0 = h[0];
					int v0 = v[0];
					int v1 = v[1];
					
					ans[h[0]][v[0]] = 1;
					ans[h[0]][v[1]] = 1;
					
					if(query() == 2 * N){
						load(h0,v0,false);
						load(h0,v1,false);
					}
					else{
						if(check(h[0],v[0])){
							load(h0,v0,true);
						}
						else{
							load(h0,v1,true);
						}
					}
				}
				else if(h.size() >= 2 && v.size() <= 2){
					reset();
					
					ans[h[0]][v[0]] = 1;
					ans[h[1]][v[0]] = 1;
					
					int h0 = h[0];
					int h1 = h[1];
					int v0 = v[0];
					
					if(query() == 2 * N){
						load(h0,v0,true);
						load(h1,v0,true);
					}
					else{
						if(!check(h[0],v[0])){
							load(h0,v0,false);
						}
						else{
							load(h1,v0,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;
					
					remove(h0,v1,true);
					remove(h0,v1,false);
					remove(h1,v1,true);
				}
				else if(ii == make_pair(2,1)){
					load(h1,v1,true);
					
					vector<pair<int,int>> temp = {{h0,v0}, {h0,v1}};
					
					chain = temp;
					
					remove(h0,v0,true);
					remove(h0,v0,false);
					remove(h0,v1,false);
				}
			}
		}
		
		
	}
	
	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();
	if(bug){
		printf("\n");
		//
		for(int i = 0; i < N; i++){
			for(int j = 0; j < N; j++){
				printf("%d",debug[i][j]);
			}
			printf("\n");
		}
		printf("\n");
		for(int i = 0; i < N; i++){
			for(int j = 0; j < N; j++){
				if(!ans[i][j]) printf("#");
				else printf("%d",debug[i][j]);
			}
			printf("\n");
		}
	}
	
	//if(debugnum() != N * N) break;
	
	//}
}	

Compilation message (stderr)

Main.cpp: In function 'int debugnum()':
Main.cpp:51:18: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
   51 |         printf("%d %d\n",v.size(),h.size());
      |                 ~^       ~~~~~~~~
      |                  |             |
      |                  int           std::vector<int>::size_type {aka long unsigned int}
      |                 %ld
Main.cpp:51:21: warning: format '%d' expects argument of type 'int', but argument 3 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
   51 |         printf("%d %d\n",v.size(),h.size());
      |                    ~^             ~~~~~~~~
      |                     |                   |
      |                     int                 std::vector<int>::size_type {aka long unsigned int}
      |                    %ld
Main.cpp: In function 'int query()':
Main.cpp:67:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |         if(!bug) scanf(" %d",&h);
      |                  ~~~~~^~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:200:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  200 | int main(){scanf(" %d",&N);
      |            ~~~~~^~~~~~~~~~

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