Submission #1192689

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192689		Nomio	Light Bulbs (EGOI24_lightbulbs)	C++17	57.48 / 100	348 ms	492 KiB

Main

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

int n;
set<int> row, col;

int ask(vector<pair<int, int>> &v) {
	vector<vector<int>> A(n, vector<int> (n, 0));
	for(pair<int, int> p : v) {
		int a = p.first;
		int b = p.second;
		A[a][b] = 1;
	}
	cout << "?" << endl;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			cout << A[i][j];
		}
		cout << endl;
	}
	int x;
	cin >> x;
	return x;
}

void answer(vector<pair<int, int>> &v) {
	vector<vector<int>> A(n, vector<int> (n, 0));
	for(pair<int, int> p : v) {
		int a = p.first;
		int b = p.second;
		A[a][b] = 1;
	}
	cout << "! " << endl;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			cout << A[i][j];
		}
		cout << endl;
	}
}

int main() {
	cin >> n;
	for(int i = 0; i < n; i++) {
		row.insert(i);
		col.insert(i);
	}
	vector<pair<int, int>> q;
	q.push_back({0, 0});
	q.push_back({1, 0});
	int x = ask(q);
	int bef = x;
	pair<int, int> bosoo = {0, 0}, hevtee = {0, 0};
	set<int> hev[n], bos[n];
	bool ok = 0;
	if(x == n * 2) {
		hev[0].insert(0);
		hev[1].insert(0);
		row.erase(0);
		row.erase(1);
		ok = 1;
	} else if(x == n) {
		bos[0].insert(0);
		bos[0].insert(1);
		col.erase(0);
		ok = 1;
	}
	bool is_hev = 1;
	for(int i = 2; i < n; i++) {
		q.push_back({i, 0});
		int x = ask(q);
		if(x < bef + n - 1) {
			bos[0].insert(i);
			is_hev = 0;
			bef = x;
		} else {
			bef = x;
			hev[i].insert(0);
			row.erase(i);
			is_hev = 1;
		}
	}
	if(!ok) {
		q.clear();
		q.push_back({n - 1, 0});
		q.push_back({0, 0});
		x = ask(q);
		if(is_hev) {
			if(x == n * 2) {
				hev[0].insert(0);
				bos[0].insert(1);
				row.erase(0);
				col.erase(0);
			} else {
				bos[0].insert(0);
				hev[1].insert(0);
				row.erase(1);
				col.erase(0);
			}
		} else {
			if(x == n) {
				bos[0].insert(0);
				hev[1].insert(0);
				row.erase(1);
				col.erase(0);
			} else {
				hev[0].insert(0);
				bos[0].insert(1);
				row.erase(0);
				col.erase(0);
			}
		}
	}
	if(row.size() == 0) {
		q.clear();
		for(int i = 0; i < n; i++) {
			if(!hev[i].empty()) q.push_back({i, *hev[i].begin()});
		}
		answer(q);
		return 0;
	}
	ok = 1;
	for(int X : row) {
		for(int Y : bos[0]) {
			bosoo = {Y, 0};
		}
		q.clear();
		q.push_back(bosoo);
		for(int i = 1; i < n; i++) {
			q.push_back({X, i});
		}
		int x = ask(q);
		if(x == n * n) {
			ok = 0;
			answer(q);
			return 0;
		}
		int l = 1, r = n - 1;
		while(l < r) {
			int mid = (l + r) / 2;
			q.clear();
			q.push_back(bosoo);
			for(int i = l; i <= mid; i++) {
				q.push_back({X, i});
			}
			int x = ask(q);
			if(x < (mid - l + 2) * n) r = mid;
			else l = mid + 1; 
		}
		hev[X].insert(l);
	} 
	q.clear();
	if(ok) {
		for(int i = 0; i < n; i++) {
			if(!hev[i].empty()) q.push_back({i, *hev[i].begin()});
		}
		answer(q);
		return 0;
	}
	q.push_back({0, 0});
	q.push_back({0, 1});
	x = ask(q);
	bef = x;
	if(x == n * 2) {
		bos[0].insert(0);
		bos[1].insert(0);
		col.erase(0);
		col.erase(1);
		ok = 1;
	} else if(x == n) {
		hev[0].insert(0);
		hev[0].insert(1);
		row.erase(0);
		ok = 1;
	}
	is_hev = 1;
	for(int i = 2; i < n; i++) {
		q.push_back({0, i});
		int x = ask(q);
		if(x < bef + n - 1) {
			hev[0].insert(i);
			is_hev = 1;
			bef = x;
		} else {
			bef = x;
			bos[i].insert(0);
			col.erase(i);
			is_hev = 0;
		}
	}
	if(!ok) {
		q.clear();
		q.push_back({0, n - 1});
		q.push_back({0, 0});
		x = ask(q);
		if(!is_hev) {
			if(x == n * 2) {
				bos[0].insert(0);
				hev[0].insert(1);
				row.erase(0);
				col.erase(0);
			} else {
				bos[1].insert(0);
				hev[0].insert(1);
				row.erase(0);
				col.erase(1);
			}
		} else {
			if(x == n) {
				bos[1].insert(0);
				hev[0].insert(0);
				row.erase(0);
				col.erase(1);
			} else {
				hev[0].insert(1);
				bos[0].insert(0);
				row.erase(0);
				col.erase(0);
			}
		}
	}
	ok = 1;
	for(int X : col) {
		for(int Y : hev[0]) {
			hevtee = {0, Y};
		}
		q.clear();
		q.push_back(hevtee);
		for(int i = 1; i < n; i++) {
			q.push_back({i, X});
		}
		int x = ask(q);
		if(x == n * n) {
			ok = 0;
			break;
		}
		int l = 1, r = n - 1;
		while(l < r) {
			int mid = (l + r) / 2;
			q.clear();
			q.push_back(hevtee);
			for(int i = l; i <= mid; i++) {
				q.push_back({i, X});
			}
			int x = ask(q);
			if(x < (mid - l + 2) * n) r = mid;
			else l = mid + 1; 
		}
		bos[X].insert(l);
	} 
	q.clear();
	if(ok) {
		for(int i = 0; i < n; i++) {
			if(!bos[i].empty()) q.push_back({*bos[i].begin(), i});
		}
		answer(q);
	}
	return 0;
}

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