Submission #1313148

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313148		salmon	Light Bulbs (EGOI24_lightbulbs)	C++20	11 / 100	1 ms	408 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;
bool bug = false;
int debug[110][110];
int ohorz = false;

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(ohorz){
		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){
		ohorz = true;
	}
	else{
		if(buf == num1){
			ohorz = true;
		}
		else{
			ohorz = false;
		}
	}
	
	if(N < 10){
	
		while(!h.empty() && !v.empty() || !chain.empty()){
			if(N < 10){
				load(h[0],v[0],check(h[0],v[0]));
				continue;
			}	
		}
		
		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();
		return 0;
	}
	
	bool die = true;
	bool rotated = false;

	for(int i = 0; i < 40; i++){
		if(rng() % 2 <=5){
			reset();
			
			shuffle(h.begin(),h.end(),rng);
			
			for(int i = 0; i < 10; i++){
				for(int j = 0; j < N; j++){
					ans[h[i]][j] = 1;
				}
			}
			
			if(query() == N * N){
				die = false;
				break;
			}
		}
		else{
			reset();
			
			shuffle(v.begin(),v.end(),rng);
			
			for(int i = 0; i < 10; i++){
				for(int j = 0; j < N; j++){
					ans[j][v[i]] = 1;
				}
			}
			
			if(query() == N * N){
				die = false;
				rotated = true;
				break;
			}
		}
	}
	
	int it = 0;
	int dit = 0;
	
	while(!h.empty() && !v.empty()){
		if(!rotated){
			int s = 0;
			int e = min((int)v.size() - 1,7);
			
			reset();
			for(int j = s; j <= e; j++){
				ans[h[it]][v[j]] = 1;
			}
			
			if(query() == N * (e - s + 1)){
				for(int i = 0; i <= e; i++){
					load(h[it],v[0],false);
				}
				continue;
			}
			
			while(s != e){
				int m = (s + e)/2;
				
				reset();
				for(int i = s; i <= m; i++){
					ans[h[it]][v[i]] = 1;
				}
				
				if(s == m){
					if(check(h[it],v[m])){
						e = m;
					}
					else{
						s = m + 1;
					}
					continue;
				}
				
				int num = query();
				
				if(num % N == 0 && num != N){
					s = m + 1;
				}
				else{
					e = m;
				}
			}
			
			load(h[it],v[s],true);
		}
		else{
			int num = 0;
			
			printf("%d",1/num);
		}
	}
	
	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];
			}
		}
	}
	
	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:50:18: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
   50 |         printf("%d %d\n",v.size(),h.size());
      |                 ~^       ~~~~~~~~
      |                  |             |
      |                  int           std::vector<int>::size_type {aka long unsigned int}
      |                 %ld
Main.cpp:50:21: warning: format '%d' expects argument of type 'int', but argument 3 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
   50 |         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:66:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |         if(!bug) scanf(" %d",&h);
      |                  ~~~~~^~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:201:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  201 | int main(){scanf(" %d",&N);
      |            ~~~~~^~~~~~~~~~

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