oj.uz

Submission #1113386

# Submission time Handle Problem Language Result Execution time Memory
1113386 2024-11-16T14:00:45 Z Nonoze Light Bulbs (EGOI24_lightbulbs) C++17
0 / 100
 1 ms 504 KB 
#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 (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);
}

Subtask #1
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Incorrect 1 ms 336 KB The lamps do not light up the entire grid
10 Halted 0 ms 0 KB -

Subtask #2
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Incorrect 1 ms 336 KB The lamps do not light up the entire grid
10 Halted 0 ms 0 KB -

Subtask #3
0 / 78.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 504 KB Output is correct
9 Incorrect 1 ms 336 KB The lamps do not light up the entire grid
10 Halted 0 ms 0 KB -