제출 #1192685

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1192685		khangai11	Light Bulbs (EGOI24_lightbulbs)	C++20	0 / 100	4064 ms	416 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 << "?\n";
	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 << "!\n";
	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};
	vector<set<int>> hev(n), bos(n);
	//while(1);	OK
	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(1);
//		bos[0].insert(0);
		col.erase(0);
		ok = 1;
	}
	while(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()});
//			else cout << "HOHOHOHOHOH" << '\n';
		}
		answer(q);
		return 0;
	}
	ok = 1;
	for(int X : row) {
		for(int Y : bos[0]) {
			bosoo = {Y, 0};
		}
//		cout << X << " : " << bosoo.first << ' ' << bosoo.second << '\n';
		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;
			break;
		}
		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);
	} 
//	for(int i = 0; i < n; i++) {
//		cout << i << " : ";
//		for(int x : hev[i]) {
//			cout << x << ' ';
//		}
//		cout << '\n';
//	}
	q.clear();
	if(ok) {
		for(int i = 0; i < n; i++) {
			if(!hev[i].empty()) q.push_back({i, *hev[i].begin()});
//			else cout << "HEHEHEHEHEHEH" << '\n';
		}
		answer(q);
		return 0;
	}
//	cout << "_______" << '\n';
	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: 0 / 11
• Subtask 2: 0 / 11
• Subtask 3: 0 / 78