Submission #1176183

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176183		uranhishig	Light Bulbs (EGOI24_lightbulbs)	C++20	22 / 100	79 ms	448 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(),(a).end()
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)

const int H = 0, V = 1;
const int mod = 1e9 + 7;
const int mx = 3e5 + 5;
vector<string> c;
vector<string> b;

int n;

int calc(vector<pair<int, int>> v) {
	vector<vector<bool>> room(n, vector<bool>(n, 0));
	for (auto r : v) {
		int i = r.first, j = r.second;
		if (b[i][j] == 'V') {
			for (int ii = 0; ii < n; ii++) room[ii][j] = 1;
		} 
		else {
			for (int jj = 0; jj < n; jj++) room[i][jj] = 1;
		}
	}
	int res = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (room[i][j]) res++;
		}
	}
	return res;
}

int ask(vector<pair<int, int>> v) {
	#ifdef LOCAL
		return calc(v);
	#endif
	vector<string> a(n, string(n, '0'));
	for (auto x : v) a[x.ff][x.ss] = '1';
	cout << "?" << endl;
	for (int i = 0; i < n; i++) {
		cout << a[i] << endl;
	}
	int res; cin >> res;
	return res;
}
	
void preprocess() {
	int a = ask({{0, 0}, {0, 1}});

	if (a == 2 * n) {
		c[0][0] = 'V';
		c[0][1] = 'V';
		return;
	}
	if (a == n) {
		c[0][0] = 'H';
		c[0][1] = 'H';
		return;
	}
	a = ask({{0, 0}, {0, 2}});
	if (a == 2 * n) {
		c[0][0] = 'V';
		c[0][1] = 'H';
		c[0][2] = 'V';
		return;
	}
	if (a == n) {
		c[0][0] = 'H';
		c[0][1] = 'V';
		c[0][2] = 'H';
		return;
	}

	a = ask({{0, 1}, {0, 2}});
	if (a == 2 * n) {
		c[0][0] = 'H';
		c[0][1] = 'V';
		c[0][2] = 'V';
		return;
	}
	if (a == n) {
		c[0][0] = 'V';
		c[0][1] = 'H';
		c[0][2] = 'H';
		return;
	}
}

void find(int i, int j) {
	if (c[i][j] != '*') return;
	int a = ask({{0, 0}, {i, j}});
	if (a == n || a == 2 * n) {
		c[i][j] = c[0][0];
	}
	else {
		if (c[0][0] == 'H') {
			c[i][j] = 'V';
		}
		else {
			c[i][j] = 'H';
		}
	}
	return;
}

int main() {
	#ifdef LOCAL
	freopen("in.txt", "r", stdin);
	#endif
	cin >> n;
	c.resize(n, string(n, '*'));
	#ifdef LOCAL
		b.resize(n);
		for (int i = 0; i < n; i++) cin >> b[i];
	#endif
	preprocess();
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			find(i, j);
		}
	}
	
	vector<string> ans(n, string(n, '0'));
	bool hevteeCheck = true;
	for (int i = 0; i < n; i++) {
		bool cur = false;
		for (int j = 0; j < n; j++) {
			if (c[i][j] == 'H') {
				cur = true;
				break;
			}
		}
		if (cur == false) {
			hevteeCheck = false;
			break;
		}
	}
	if (hevteeCheck) {
		for (int i = 0; i < n; i++) {
			int x = 0;
			for (int j = 0; j < n; j++) {
				if (c[i][j] == 'H' and x == 0) {
					x++;
					ans[i][j] = '1';
				}
				else if (x > 0) {
					break;
				}
			}
		}
	}
	else {
		for (int j = 0; j < n; j++) {
			int x = 0;
			for (int i = 0; i < n; i++) {
				if (c[i][j] == 'V' and x == 0) {
					x++;
					ans[i][j] = '1';
				}
				else if (x > 0){
					break;
				}
			}
		}
	}
	cout << '!' << endl;
	for (int i = 0; i < n; i++) {
		cout << ans[i] << endl;
	}																	
	return 0;
}

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