oj.uz

Submission #1048250

# Submission time Handle Problem Language Result Execution time Memory
1048250 2024-08-08T06:01:46 Z 박영우(#11091) Light Bulbs (EGOI24_lightbulbs) C++17
0 / 100
 1 ms 344 KB 
//#define LOCAL
#include <bits/stdc++.h>
#include <cassert>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 110
#define MAXQ 101010
#define INF 1'000'000'100'000'000'000
#define bb ' '
#define ln '\n'
#define Ln '\n'
#define MOD 1000000007
#define TC 1
#ifdef LOCAL
#define DEBUG(a) cout<<a
#define TEST true
#else
#define DEBUG(...) 1234
#define TEST false
#endif

int mp[MAX][MAX];
int ans[MAX];
int N;
int dp[MAX][MAX];
int arr[MAX][MAX];
int query(char x = '?') {
	cout << x << endl;
	int i, j;
	for (i = 0; i < N; i++) {
		for (j = 0; j < N; j++) cout << arr[i][j];
		cout << endl;
	}
	if (x == '?') {
		int x;
		cin >> x;
		return x;
	}
	return 0;
}
int test(int r, int c) {
	if (dp[r][c]) return dp[r][c];
	int i, j;
	cout << '?' << endl;
	for (i = 0; i < N; i++) {
		for (j = 0; j < N; j++) {
			if (i <= r && j == c) cout << 1;
			else cout << 0;
		}
		cout << endl;
	}
	int x;
	cin >> x;
	return dp[r][c] = x;
}
int get(int sum, int mul) {
	int i;
	for (i = 0; i <= sum; i++) {
		int j = sum - i;
		if (i * j == mul) return i;
	}
	assert(0);
	return 0;
}
int chk[MAX];
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> N;
	int i;
	for (i = 0; i < N; i++) {
		int l, r;
		l = 1;
		r = N;
		while (r - l > 1) {
			if (r == 1) break;
			int m = l + r >> 1;
			int res = test(m, i);
			if (res == N * (m + 1)) l = m;
			else r = m;
		}
		if (l == 1) {
			chk[i] = 1;
			continue;
		}
		if (r == N) {
			int a, b;
			cout << '!' << endl;
			for (a = 0; a < N; a++) {
				for (b = 0; b < N; b++) {
					if (b == i) cout << 1;
					else cout << 0;
				}
				cout << endl;
			}
			return 0;
		}
		ans[i] = r;
	}
	vector<int> vc, nc;
	for (i = 0; i < N; i++) if (chk[i]) vc.push_back(i);
	for (i = 0; i < N; i++) if (!chk[i]) nc.push_back(i);
	if (nc.empty()) {
		int x, y, z;
		int sz = vc.size();
		x = vc[sz - 1], y = vc[sz - 2], z = vc[sz - 3];
		int chk = 0;
		for (ans[x] = 0; ans[x] <= 1; ans[x]++) {
			for (ans[y] = 0; ans[y] <= 1; ans[y]++) {
				for (ans[z] = 0; ans[z] <= 1; ans[z]++) {
					arr[ans[x]][x] = arr[ans[y]][y] = arr[ans[z]][z] = 1;
					if (query() == N * 3) chk = 1;
					arr[ans[x]][x] = arr[ans[y]][y] = arr[ans[z]][z] = 0;
					if (chk) break;
				}
				if (chk) break;
			}
			if (chk) break;
		}
		vc.pop_back();
		vc.pop_back();
		vc.pop_back();
		nc.push_back(x);
		nc.push_back(y);
		nc.push_back(z);
	}
	for (auto x : vc) {
		arr[ans[nc[0]]][nc[0]] = 1;
		arr[0][x] = 1;
		if (query() == N * 2) ans[x] = 0;
		else ans[x] = 1;
		arr[ans[nc[0]]][nc[0]] = 0;
		arr[0][x] = 0;
	}
	for (i = 0; i < N; i++) arr[ans[i]][i] = 1;
	query('!');
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:82:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   82 |    int m = l + r >> 1;
      |            ~~^~~

Subtask #1
0.0 / 11.0

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

Subtask #2
0.0 / 11.0

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

Subtask #3
0 / 78.0

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