Submission #1113393

#TimeUsernameProblemLanguageResultExecution timeMemory
1113393NonozeLight Bulbs (EGOI24_lightbulbs)C++17
80 / 100
133 ms1120 KiB
#include <bits/stdc++.h>
using namespace std;

#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define cmin(a, b) a=min(a, b)
#define cmax(a, b) a=max(a, b)
#define fi first
#define se second
#define pb push_back
#define mp make_pair

#define int long long

void solve();

signed main() {
	ios::sync_with_stdio(0); cin.tie(0);
	solve();
	return 0;
}



int ask(vector<vector<int>>& grid) {
	cout << "?" << endl;
	for (auto u: grid) {
		for (auto v: u) cout << v ;
		cout << endl;
	}
	int ans; cin >> ans;
	return ans;
}


int end(vector<vector<int>>& grid) {
	cout << "!" << endl;
	for (auto u: grid) {
		for (auto v: u) cout << v ;
		cout << endl;
	}
	exit(0);
}

int n, m, q;


void solve() {
	cin >> n;
	vector<vector<int>> grid(n, vector<int>(n)), is(n, vector<int>(n, -1)); // 0: column, 1: line
	set<int> col, line; for (int i=0; i<n; i++) col.insert(i), line.insert(i);
	set<pair<int, int>> bestc, bestl;
	{
		for (int i=0; i<n; i++) grid[0][i]=1;

		int x=ask(grid); grid[0][0]=0; int y=ask(grid);
		if (x==n*n) {
			grid[0][0]=1;
			end(grid);
		}
		if (y==n*(n-1) && x==y+1) x=y;
		if (x==y) is[0][0]=1, line.erase(0), bestl.insert({0, 0});
		else is[0][0]=0, col.erase(0), bestc.insert({0, 0});

		for (int i=0; i<n; i++) grid[0][i]=0;
	}
	for (int i=0; i<n; i++) {
		for (int j=0; j<n; j++) if (col.count(j) && line.count(i)) {
			grid[0][0]=1, grid[i][j]=1;
			if (ask(grid)==2*n) is[i][j]=is[0][0];
			else is[i][j]=1-is[0][0];
			if (is[i][j]) line.erase(i), bestl.insert({i, j});
			else col.erase(j), bestc.insert({i, j});
			grid[0][0]=0, grid[i][j]=0;
		}
	}
	if (!col.empty()) swap(bestl, bestc);
	for (auto u: bestc) grid[u.fi][u.se]=1;
	end(grid);
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...