oj.uz

Submission #1101669

# Submission time Handle Problem Language Result Execution time Memory
1101669 2024-10-16T14:55:50 Z NoMercy Colors (BOI20_colors) C++17
0 / 100
 1 ms 336 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int ask (ll x) {
	cout << "? " << x << endl;
	int res;
	cin >> res;
	return res;
}

int32_t main () {

	// ios_base::sync_with_stdio(0); 
	// cin.tie(0); 
	// cout.tie(0); 

	ll N;
	cin >> N;
	ll ind = 1, dir = 1, cur = 1;
	ll lo = 1, hi = N;
    while (lo < hi) {
        ll mid = (lo + hi) >> 1;
        if (cur + dir * mid >= 1) {
			cur += dir * mid;
		} else {
			ind += 1 - (cur + dir * mid);
			cur = 1;
		}
        lo = mid + 1;
        dir = -dir;
    }
    ask (ind);
	lo = 1;
	hi = N;
	while (lo < hi) {
		ll mid = (lo + hi) >> 1;
		// cout << lo << " " << mid << " " << hi << " " << ind << "\n";
		if (ind - mid >= 1) {
			if (ask (ind - mid) == 1) {
				hi = mid;
			} else {
				lo = mid + 1;
			}
			ind = ind - mid;
		} else if (ind + mid <= N) {
			if (ask (ind + mid) == 1) {
				hi = mid;
			} else {
				lo = mid + 1;
			}
			ind = ind + mid;
		} else {
			if (ind - 1 >= N - ind) {
				if (ask(1) == 1) {
					hi = ind - 1;
				} else {
					lo = ind;
				}
				ind = 1;
			} else {
				if (ask(N) == 1) {
					hi = N - ind;
				} else {
					lo = N - ind + 1;
				}
				ind = N;
			}
		}
	}
	cout << "= " << hi << endl;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB OK (4 queries)
2 Correct 1 ms 336 KB OK (7 queries)
3 Incorrect 1 ms 336 KB Hair color 4 was used multiple times
4 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB OK (4 queries)
2 Correct 1 ms 336 KB OK (7 queries)
3 Incorrect 1 ms 336 KB Hair color 4 was used multiple times
4 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB OK (4 queries)
2 Correct 1 ms 336 KB OK (7 queries)
3 Incorrect 1 ms 336 KB Hair color 4 was used multiple times
4 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB OK (4 queries)
2 Correct 1 ms 336 KB OK (7 queries)
3 Incorrect 1 ms 336 KB Hair color 4 was used multiple times
4 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB OK (4 queries)
2 Correct 1 ms 336 KB OK (7 queries)
3 Incorrect 1 ms 336 KB Hair color 4 was used multiple times
4 Halted 0 ms 0 KB -