Submission #1148953

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148953		Pwo	Zagrade (COI20_zagrade)	C++20	0 / 100	3055 ms	589824 KiB

zagrade

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 100005;

int n, q;
vector<pair<bitset<N>, int>> u, v;

int32_t main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> q;
	v.emplace_back(0, 0);
	v.emplace_back(1, 1);
	for (int i = 2; i <= n; i++) {
		cout << "? " << i - 1 << ' ' << i << '\n' << flush;
		int res; cin >> res;
		u.clear(); u.shrink_to_fit();
		for (auto [s, c] : v) {
			if (c * 2 > n) continue;
			if (res) {
				if (s.test(i - 2) == 0) {
					s.set(i - 1);
					u.emplace_back(s, c + 1);
				}
			} else {
				if (s.test(i - 2) == 1) {
					u.emplace_back(s, c);
					bitset<N> cpy = s;
					cpy.set(i - 1);
					u.emplace_back(cpy, c + 1);
				} else {
					u.emplace_back(s, c);
				}
			}
		}
		swap(u, v);
	}
	
	for (auto [s, c] : v) {
		if (c * 2 != n) continue;
		cout << "! ";
		for (int i = 0; i < n; i++) {
			if (s.test(i)) cout << ')';
			else cout << '(';
		}
		cout << flush;
		break;
	}
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 7
• Subtask 3: 0 / 57
• Subtask 4: 0 / 22