Submission #1303446

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303446		_asunaa	Colors (BOI20_colors)	C++20	67 / 100	1 ms	448 KiB

Colors

#include <bits/stdc++.h>
using namespace std;
long long i, j, l, r, mid, p, q, k, t, n, m, a, b, c, d, ans, cnt, res;
const long long mod = 999993143, mod2 = 999993469;
string s;
bool check;
long double cur;
map <long long, long long> mp;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	if (n > 64){
		l = 1;
		r = n;
		a = 1;
		b = n;
		res = n / 3;
		mp[res] = 1;
		cout << "? " << res << endl;
		cin >> d;
		cnt = 0;
		t = res;
		while (l < r){
			mid = (l + r) / 2;
			if (cnt % 2 == 0){
				res += mid;
			}
			else{
				res -= mid;
			}
			check = false;
			if (t == 1){
				if (mp[n] == 0){
					res = n;
					check = true;
				}
			}
			if (t == n){
				if (mp[1] == 0){
					res = 1;
					check = true;
				}
			}
			if (check == false){
				if (mp[res] == 1 || res <= 0 || res > n){
					res -= 1;
					if (mp[res] == 1 || res <= 0 || res > n){
						res += 2;
						if (mp[res] == 1 || res <= 0 || res > n){
							res -= 3;
							if (mp[res] == 1 || res <= 0 || res > n){
								res += 4;
								if (mp[res] == 1 || res <= 0 || res > n){
									res -= 5;
									if (mp[res] == 1 || res <= 0 || res > n){
										res += 6;
										if (mp[res] == 1 || res <= 0 || res > n){
											break;
										}
									}
								}
							}
						}
					}
				}
			}
			mp[res] = 1;
			cout << "? " << res << endl;
			cin >> d;
			if (d == 0){
				a = max(a, abs(t - res) + 1);
				l = a;
			}
			else{
				b = min(b, abs(t - res));
				r = b;
			}
			c = a;
			d = b;
			a = min(c, d);
			b = max(c, d);
			cnt += 1;
			t = res;
		}
		cout << "= " << a << endl;
	}
	else{
		ans = 0;
		l = 2;
		r = n;
		cout << "? 1" << endl;
		cin >> d;
		for (i = 2; i <= n; i += 1){
			if (i % 2 == 1){
				cout << "? " << l << endl;
				l += 1;
			}
			else{
				cout << "? " << r << endl;
				r -= 1;
			}
			cin >> d;
			if (d == 0){
				break;
			}
			else{
				ans += 1;
			}
		}
		cout << "= " << n - ans << endl;
	}
}

• Subtask 1: 9 / 9
• Subtask 2: 13 / 13
• Subtask 3: 21 / 21
• Subtask 4: 24 / 24
• Subtask 5: 0 / 33