Submission #1303397

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303397		_asunaa	Colors (BOI20_colors)	C++20	9 / 100	1 ms	424 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;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	if (n > 64){
		a = 1;
		b = n;
		c = n / 2;
		l = 0;
		r = c - 1;
		t = -1;
		while (l <= r && a < b){
			mid = (l + r) / 2;
			if (n % 2 == 1 && mid == c - 1){
				cout << "? " << n << endl;
				cin >> d;
				if (t != -1){
					if (d == 0){
						a = max(a, abs(n - t) + 1);
					}
					else{
						b = min(b, abs(n - t));
					}
				}
				t = n;
				cout << "? " << 1 << endl;
				cin >> d;
				if (t != -1){
					if (d == 0){
						a = max(a, abs(1 - t) + 1);
					}
					else{
						b = min(b, abs(1 - t));
					}
				}
				t = 1;
				cout << "? " << n - 1 << endl;
				cin >> d;
				if (t != -1){
					if (d == 0){
						a = max(a, abs((n - 1) - t) + 1);
					}
					else{
						b = min(b, abs((n - 1) - t));
					}
				}
				break;
			}
			else{
				cout << "? " << c - mid << endl;
				cin >> d;
				if (t != -1){
					if (d == 0){
						a = max(a, abs((c - mid) - t) + 1);
					}
					else{
						b = min(b, abs((c - mid) - t));
					}
				}
				t = c - mid;
				cout << "? " << c + mid + 1 << endl;
				cin >> d;
				if (t != -1){
					if (d == 0){
						a = max(a, abs((c + mid + 1) - t) + 1);
						l = mid + 1;
					}
					else{
						b = min(b, abs((c + mid + 1) - t));
						r = mid - 1;
					}
				}
				t = c + mid + 1;
			}
		}
		cout << "= " << a << endl;
//		cout << "= " << b << 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: 0 / 13
• Subtask 3: 0 / 21
• Subtask 4: 0 / 24
• Subtask 5: 0 / 33