oj.uz

Submission #999688

# Submission time Handle Problem Language Result Execution time Memory
999688 2024-06-16T05:05:19 Z Mr_Husanboy Colors (BOI20_colors) C++17
0 / 100
 0 ms 344 KB 
#include<bits/stdc++.h>

using namespace std;
#define ll long long
#define all(a) (a).begin(), (a).end()

long long C;
set<ll> st;
ll last = -1;
int _query = 0;

int ask(ll x){
	_query++;
	cout  << "? " << x << endl;
	if(st.count(x)){
		cout << " Used before!" << endl;
		exit(0);
	}
	st.insert(x);
	int res; 
#ifdef LOCAL
	res = (last == -1 || llabs(x - last) >= C ? 1 : 0);
#else
	cin >> res;
#endif
	last = x;
	return res;
}

void out(ll x){
	cout << "= " << x << endl;
#ifdef LOCAL
	assert(x == C);
	cout << _query << " queries called!";
#endif
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	ll n; cin >> n;
#ifdef LOCAL
	cin >> C;
#endif
	ll l = 0, r = n;
	ll cur = 1;
	vector<ll> q;
	while(r - l > 1){
		ll m = (l + r) / 2;
		q.push_back(m);
		l = m + 1;
	}
	reverse(all(q));
	for(auto u : q){
		if(cur + u <= n) cur += u;
		else cur -= u;
	}

	ask(cur);

	l = 0, r = n;
	while(r - l > 1){
		ll m = (l + r) / 2;
		if(st.count(cur + m) || cur + m > n){
			cur -= m;
		}else cur += m;
		if(ask(cur)){
			r = m;
		}else l = m;
	}
	out(r);
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB OK (4 queries)
2 Correct 0 ms 344 KB OK (7 queries)
3 Correct 0 ms 344 KB OK (4 queries)
4 Correct 0 ms 344 KB OK (5 queries)
5 Correct 0 ms 344 KB OK (5 queries)
6 Correct 0 ms 344 KB OK (7 queries)
7 Correct 0 ms 344 KB OK (7 queries)
8 Correct 0 ms 344 KB OK (6 queries)
9 Correct 0 ms 344 KB OK (7 queries)
10 Correct 0 ms 344 KB OK (4 queries)
11 Correct 0 ms 344 KB OK (5 queries)
12 Runtime error 0 ms 344 KB Execution killed with signal 13
13 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB OK (4 queries)
2 Correct 0 ms 344 KB OK (7 queries)
3 Correct 0 ms 344 KB OK (4 queries)
4 Correct 0 ms 344 KB OK (5 queries)
5 Correct 0 ms 344 KB OK (5 queries)
6 Correct 0 ms 344 KB OK (7 queries)
7 Correct 0 ms 344 KB OK (7 queries)
8 Correct 0 ms 344 KB OK (6 queries)
9 Correct 0 ms 344 KB OK (7 queries)
10 Correct 0 ms 344 KB OK (4 queries)
11 Correct 0 ms 344 KB OK (5 queries)
12 Runtime error 0 ms 344 KB Execution killed with signal 13
13 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB OK (4 queries)
2 Correct 0 ms 344 KB OK (7 queries)
3 Correct 0 ms 344 KB OK (4 queries)
4 Correct 0 ms 344 KB OK (5 queries)
5 Correct 0 ms 344 KB OK (5 queries)
6 Correct 0 ms 344 KB OK (7 queries)
7 Correct 0 ms 344 KB OK (7 queries)
8 Correct 0 ms 344 KB OK (6 queries)
9 Correct 0 ms 344 KB OK (7 queries)
10 Correct 0 ms 344 KB OK (4 queries)
11 Correct 0 ms 344 KB OK (5 queries)
12 Runtime error 0 ms 344 KB Execution killed with signal 13
13 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB OK (4 queries)
2 Correct 0 ms 344 KB OK (7 queries)
3 Correct 0 ms 344 KB OK (4 queries)
4 Correct 0 ms 344 KB OK (5 queries)
5 Correct 0 ms 344 KB OK (5 queries)
6 Correct 0 ms 344 KB OK (7 queries)
7 Correct 0 ms 344 KB OK (7 queries)
8 Correct 0 ms 344 KB OK (6 queries)
9 Correct 0 ms 344 KB OK (7 queries)
10 Correct 0 ms 344 KB OK (4 queries)
11 Correct 0 ms 344 KB OK (5 queries)
12 Runtime error 0 ms 344 KB Execution killed with signal 13
13 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB OK (4 queries)
2 Correct 0 ms 344 KB OK (7 queries)
3 Correct 0 ms 344 KB OK (4 queries)
4 Correct 0 ms 344 KB OK (5 queries)
5 Correct 0 ms 344 KB OK (5 queries)
6 Correct 0 ms 344 KB OK (7 queries)
7 Correct 0 ms 344 KB OK (7 queries)
8 Correct 0 ms 344 KB OK (6 queries)
9 Correct 0 ms 344 KB OK (7 queries)
10 Correct 0 ms 344 KB OK (4 queries)
11 Correct 0 ms 344 KB OK (5 queries)
12 Runtime error 0 ms 344 KB Execution killed with signal 13
13 Halted 0 ms 0 KB -