QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#357124 | #5702. Colors | Dimash | 0 | 1ms | 3668kb | C++20 | 1.3kb | 2024-03-18 18:34:12 | 2024-03-18 18:34:12 |
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5 + 5, MOD = 998244353;
int LST = -1;
int ask(int x,int y){
cout << "? " << x << endl;
int a;cin >> a;
cout << "? " << y << endl;
cin >> a;
LST = y;
return a;
}
int n;
bool vis[N];
bool check(int x){
x *= -1;
if(LST != -1 && LST + x >= 1&& !vis[LST + x]){
cout << "? " << LST + x << endl;
int a;
cin >> a;
vis[LST + x] = 1;
LST += x;
return a;
}
x *= -1;
if(LST != -1 && LST + x <= n && !vis[LST + x]){
cout << "? " << LST + x << endl;
int a;
cin >> a;
vis[LST + x] = 1;
LST += x;
return a;
}
for(int i = n;i >= 1;i--){
if(i + x <= n && !vis[i] && !vis[i + x]){
vis[i] = vis[i + x] = 1;
return ask(i,i+x);
}
}
return false;
}
void test() {
cin >> n;
int l = 0,r = n;
while(r - l > 1){
int mid = (l + r) >> 1;
if(check(mid)){
r = mid;
}else
l = mid;
}
cout << "= " << r << endl;
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);
int T = 1;
// cin >> T;
while(T--){
test();
}
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 9
Accepted
time: 1ms
memory: 3580kb
input:
7 1 0 1 1
output:
? 4 ? 7 ? 2 ? 6 = 4
result:
ok OK (4 queries)
Test #2:
score: 0
Accepted
time: 1ms
memory: 3584kb
input:
49 1 0 0 0 0 1 0 0
output:
? 25 ? 49 ? 13 ? 6 ? 48 ? 3 ? 46 ? 2 = 45
result:
ok OK (8 queries)
Test #3:
score: 0
Accepted
time: 1ms
memory: 3492kb
input:
10 1 1 1 0
output:
? 5 ? 10 ? 8 ? 7 = 2
result:
ok OK (4 queries)
Test #4:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
26 1 1 1 1 1
output:
? 13 ? 26 ? 20 ? 17 ? 16 = 1
result:
ok OK (5 queries)
Test #5:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
23 1 0 1 1 1
output:
? 12 ? 23 ? 6 ? 20 ? 8 = 12
result:
ok OK (5 queries)
Test #6:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
56 0 0 1 1 0 1 1
output:
? 28 ? 56 ? 14 ? 49 ? 18 ? 51 ? 19 = 32
result:
ok OK (7 queries)
Test #7:
score: 0
Accepted
time: 1ms
memory: 3580kb
input:
52 0 0 1 0 0 1 0
output:
? 26 ? 52 ? 13 ? 45 ? 10 ? 47 ? 11 = 37
result:
ok OK (7 queries)
Test #8:
score: 0
Accepted
time: 1ms
memory: 3544kb
input:
43 1 0 0 0 0 1 1
output:
? 22 ? 43 ? 11 ? 5 ? 42 ? 2 ? 40 = 38
result:
ok OK (7 queries)
Test #9:
score: 0
Accepted
time: 1ms
memory: 3664kb
input:
46 1 0 0 0 1 0 0 0 1 1
output:
? 23 ? 46 ? 12 ? 5 ? 45 ? 8 ? 6 ? 44 ? 4 ? 43 = 39
result:
ok OK (10 queries)
Test #10:
score: 0
Accepted
time: 1ms
memory: 3500kb
input:
11 1 1 1 1
output:
? 6 ? 11 ? 9 ? 8 = 1
result:
ok OK (4 queries)
Test #11:
score: 0
Accepted
time: 1ms
memory: 3640kb
input:
14 1 0 0 0 1 0
output:
? 7 ? 14 ? 4 ? 1 ? 13 ? 2 = 12
result:
ok OK (6 queries)
Test #12:
score: 0
Accepted
time: 0ms
memory: 3668kb
input:
23 1 0 0 0 1 0 0 0
output:
? 12 ? 23 ? 6 ? 2 ? 22 ? 4 ? 1 ? 20 = 20
result:
ok OK (8 queries)
Test #13:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
47 1 0 0 0 1 1 0 0
output:
? 24 ? 47 ? 12 ? 5 ? 46 ? 8 ? 44 ? 7 = 38
result:
ok OK (8 queries)
Test #14:
score: 0
Accepted
time: 1ms
memory: 3640kb
input:
44 0 0 1 0 1 0 0
output:
? 22 ? 44 ? 11 ? 38 ? 8 ? 36 ? 7 = 30
result:
ok OK (7 queries)
Test #15:
score: 0
Accepted
time: 1ms
memory: 3636kb
input:
54 1 0 0 0 1 0 0 1 0
output:
? 27 ? 54 ? 14 ? 6 ? 53 ? 10 ? 7 ? 52 ? 8 = 45
result:
ok OK (9 queries)
Test #16:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
53 1 1 0 0 1 0 1
output:
? 27 ? 53 ? 40 ? 21 ? 43 ? 23 ? 2 = 21
result:
ok OK (7 queries)
Test #17:
score: 0
Accepted
time: 1ms
memory: 3640kb
input:
35 1 0 0 0 0 0
output:
? 18 ? 35 ? 9 ? 4 ? 34 ? 2 = 35
result:
ok OK (6 queries)
Test #18:
score: 0
Accepted
time: 1ms
memory: 3588kb
input:
37 1 0 1 0 1 1
output:
? 19 ? 37 ? 10 ? 32 ? 8 ? 31 = 23
result:
ok OK (6 queries)
Test #19:
score: -9
Wrong Answer
time: 1ms
memory: 3544kb
input:
26 1 0 0 0 0 0
output:
? 13 ? 26 ? 7 ? 3 ? 25 ? 1 = 26
result:
wrong answer Wrong guess
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
0%