Submission #1058773

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058773		Gray	Light Bulbs (EGOI24_lightbulbs)	C++17	79.97 / 100	106 ms	532 KiB

Main

// #pragma GCC optimize("O3")
// #pragma GCC target("avx2")
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <functional>
#include <map>
#include <math.h>
#include <algorithm>
#include <iostream>
#include <queue>
#include <set>
#include <utility>
#include<string>
#include <vector>
#define ll long long
#define ull unsigned ll
#define ld long double
#define ln "\n"
#define ff first
#define ss second
using namespace std;
const ll inf=2e18;
const ll MOD = 1000000007;
ll n;
ll query(vector<pair<ll, ll>> pts){
	cout << "?" << endl;
	vector<vector<ll>> out(n, vector<ll>(n));
	for (auto ch:pts){
		out[ch.ff][ch.ss]=1;
	}
	for (ll i=0; i<n; i++){
		for (ll j=0; j<n; j++) cout << out[i][j];
		cout << endl;
	}
	ll x; cin >> x; return x;
}
void solve(){
	cin >> n;
	ll ic=0, jc=0;
	vector<ll> ver(n), hor(n);
	pair<ll, ll> mv;
	{
		ll qry=query({{0, 0}, {0, 1}});
		if (qry==2*n){
			mv = {0, 1};
		}else if (qry==n){
			mv = {1, 0};
		}else{
			qry=query({{0, 0}, {0, 2}});
			if (qry==2*n){
				mv = {0, 1};
			}else if (qry==n){
				mv = {1, 0};
			}else{
				qry=query({{0, 1}, {0, 2}});
				if (qry==2*n){
					mv = {1, 0};
				}else{
					mv = {0, 1};
				}
			}
		}
	}
	if (mv==make_pair(0ll, 1ll)){
		ver[0]=0;
		jc++;
	}else{
		hor[0]=0;
		ic++;
	}
	// ll cnt=0;
	while (ic<n and jc<n){
		// cout << "Program: " << ic << " " << jc << ln;
		ll pic = ic-mv.ff, pjc=jc-mv.ss;
		ll qry=query({{pic, pjc}, {ic, jc}});
		if (qry==2*n){
			if (mv == make_pair(0ll, 1ll)){
				ver[jc]=ic;
				jc++;
			}else{
				hor[ic]=jc;
				ic++;
			}
		}else{
			swap(mv.ff, mv.ss);
			if (mv == make_pair(0ll, 1ll)){
				ver[jc]=ic;
				jc++;
			}else{
				hor[ic]=jc;
				ic++;
			}			
		}
		if (ic==n or jc==n) break;
	}
	vector<vector<ll>> ans(n, vector<ll>(n));
	// cerr << ic << " " << jc << ln;
	if (ic==n){
		for (ll i=0; i<n; i++){
			ans[i][hor[i]]=1;
		}
	}else{
		for (ll i=0; i<n; i++){
			ans[ver[i]][i]=1;
		}
	}
	
	cout << "!" << endl;
	for (ll i=0; i<n; i++){
		for (ll j=0; j<n; j++){
			cout << ans[i][j];
		}
		cout << ln;
	}
}
int main(){
	// freopen("error.f", "w", stderr);
	ios_base::sync_with_stdio(0);
	cin.tie(nullptr);
	ll t=1;
	// cin >> t;
	while (t--) solve();
}

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