QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#32861 | #866. Display of Springs | Froggygua | AC ✓ | 148ms | 3664kb | C++17 | 1.4kb | 2022-05-25 09:02:14 | 2022-05-25 09:02:16 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define N 100010
typedef long long ll;
int n;
int Ask(int a,int b,int k){
if(!b)return -1;
if(!a)return 1;
--a,--b;
cout<<"? "<<a<<' '<<b<<' '<<k<<endl;
string s;
cin>>s;
if(s=="FIRST")return -1;
if(s=="SECOND")return 1;
return 0;
}
void Report(int x){
--x;
cout<<"! "<<x<<endl;
}
class Segment_Tree{
int Len;
struct node{
int p;
}t[N<<2];
#define ls u<<1
#define rs u<<1|1
void _ins(int u,int L,int R,int id){
if(!id)return;
if(L==R){
if(!t[u].p||Ask(id,t[u].p,L)==-1){
t[u].p=id;
return;
}
}
int mid=(L+R)>>1;
if(Ask(id,t[u].p,mid)==-1){
swap(id,t[u].p);
}
if(Ask(t[u].p,id,L)==1){
_ins(ls,L,mid,id);
}
else if(Ask(t[u].p,id,R)==1){
_ins(rs,mid+1,R,id);
}
}
int _query(int u,int L,int R,int pos){
if(L==R){
return t[u].p;
}
int mid=(L+R)>>1;
int ans=t[u].p;
int x=pos<=mid?_query(ls,L,mid,pos):_query(rs,mid+1,R,pos);
if(Ask(ans,x,pos)==1)ans=x;
return ans;
}
public:
void init(int n,int _len){
Len=_len;
for(int i=1;i<=n;++i){
_ins(1,1,Len,i);
}
}
int Query(int p){
return _query(1,1,Len,p);
}
}T;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
T.init(n,100000);
cout<<"!"<<endl;
while(true){
string opt;
cin>>opt;
if(opt=="FINISH")break;
int x;
cin>>x;
Report(T.Query(x));
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3580kb
input:
3 FIRST FIRST FIRST FIRST SECOND QUESTION 2 SECOND QUESTION 6 FIRST FINISH
output:
? 1 0 50000 ? 1 0 1 ? 1 0 100000 ? 2 1 50000 ? 2 1 1 ! ? 2 1 2 ! 1 ? 2 1 6 ! 2
result:
ok Correct answer
Test #2:
score: 0
Accepted
time: 2ms
memory: 3532kb
input:
6 FIRST EQUAL FIRST FIRST SECOND FIRST SECOND FIRST SECOND FIRST SECOND FIRST SECOND FIRST SECOND FIRST SECOND FIRST SECOND FIRST SECOND FIRST SECOND QUESTION 1 SECOND SECOND SECOND SECOND QUESTION 2 EQUAL SECOND SECOND SECOND QUESTION 3 FIRST EQUAL SECOND SECOND QUESTION 4 FIRST FIRST EQUAL SECOND ...
output:
? 1 0 50000 ? 1 0 1 ? 1 0 100000 ? 2 1 50000 ? 2 1 1 ? 3 2 50000 ? 3 2 1 ? 2 1 25000 ? 2 1 1 ? 4 3 50000 ? 4 3 1 ? 3 2 25000 ? 3 2 1 ? 2 1 12500 ? 2 1 1 ? 5 4 50000 ? 5 4 1 ? 4 3 25000 ? 4 3 1 ? 3 2 12500 ? 3 2 1 ? 2 1 6250 ? 2 1 1 ! ? 2 1 1 ? 3 1 1 ? 4 1 1 ? 5 1 1 ! 1 ? 2 1 2 ? 3 2 2 ? 4 2 2 ? 5 2 ...
result:
ok Correct answer
Test #3:
score: 0
Accepted
time: 6ms
memory: 3600kb
input:
326 SECOND FIRST FIRST SECOND SECOND FIRST SECOND FIRST SECOND SECOND SECOND SECOND SECOND FIRST FIRST FIRST SECOND FIRST FIRST SECOND SECOND SECOND FIRST FIRST SECOND SECOND SECOND FIRST FIRST FIRST FIRST FIRST SECOND FIRST FIRST SECOND FIRST FIRST SECOND FIRST FIRST SECOND FIRST FIRST SECOND SECON...
output:
? 1 0 50000 ? 0 1 1 ? 0 1 100000 ? 2 0 50000 ? 0 2 1 ? 3 0 50000 ? 3 0 1 ? 0 2 25000 ? 0 2 1 ? 4 3 50000 ? 3 4 1 ? 4 0 25000 ? 0 4 1 ? 4 2 12500 ? 4 2 1 ? 4 2 25000 ? 5 3 50000 ? 3 5 1 ? 3 5 100000 ? 6 3 50000 ? 3 6 1 ? 6 0 25000 ? 0 6 1 ? 0 6 50000 ? 7 3 50000 ? 3 7 1 ? 7 0 25000 ? 0 7 1 ? 0 7 5000...
result:
ok Correct answer
Test #4:
score: 0
Accepted
time: 18ms
memory: 3648kb
input:
19 FIRST FIRST FIRST SECOND FIRST FIRST SECOND FIRST FIRST SECOND FIRST FIRST SECOND FIRST FIRST FIRST SECOND SECOND FIRST FIRST FIRST FIRST FIRST FIRST FIRST FIRST SECOND FIRST FIRST SECOND FIRST FIRST FIRST FIRST FIRST SECOND FIRST FIRST SECOND FIRST FIRST SECOND FIRST FIRST SECOND FIRST FIRST SEC...
output:
? 1 0 50000 ? 1 0 1 ? 1 0 100000 ? 2 1 50000 ? 1 2 1 ? 1 2 100000 ? 3 1 50000 ? 1 3 1 ? 1 3 100000 ? 4 1 50000 ? 1 4 1 ? 1 4 100000 ? 5 1 50000 ? 1 5 1 ? 1 5 100000 ? 6 1 50000 ? 6 1 1 ? 7 6 50000 ? 6 7 1 ? 6 7 100000 ? 8 6 50000 ? 8 6 1 ? 8 6 100000 ? 9 8 50000 ? 9 8 1 ? 9 8 100000 ? 10 9 50000 ? 9...
result:
ok Correct answer
Test #5:
score: 0
Accepted
time: 21ms
memory: 3552kb
input:
500 FIRST FIRST FIRST FIRST FIRST FIRST FIRST FIRST FIRST SECOND FIRST FIRST SECOND FIRST FIRST SECOND FIRST FIRST FIRST FIRST FIRST SECOND FIRST FIRST SECOND FIRST FIRST SECOND FIRST FIRST SECOND FIRST FIRST SECOND FIRST FIRST SECOND FIRST FIRST SECOND FIRST FIRST SECOND FIRST FIRST SECOND FIRST FI...
output:
? 1 0 50000 ? 1 0 1 ? 1 0 100000 ? 2 1 50000 ? 2 1 1 ? 2 1 100000 ? 3 2 50000 ? 3 2 1 ? 3 2 100000 ? 4 3 50000 ? 3 4 1 ? 3 4 100000 ? 5 3 50000 ? 3 5 1 ? 3 5 100000 ? 6 3 50000 ? 3 6 1 ? 3 6 100000 ? 7 3 50000 ? 7 3 1 ? 7 3 100000 ? 8 7 50000 ? 7 8 1 ? 7 8 100000 ? 9 7 50000 ? 7 9 1 ? 7 9 100000 ? 1...
result:
ok Correct answer
Test #6:
score: 0
Accepted
time: 13ms
memory: 3612kb
input:
500 EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQ...
output:
? 1 0 50000 ? 0 1 1 ? 0 1 100000 ? 2 0 50000 ? 0 2 1 ? 0 2 100000 ? 3 0 50000 ? 0 3 1 ? 0 3 100000 ? 4 0 50000 ? 0 4 1 ? 0 4 100000 ? 5 0 50000 ? 0 5 1 ? 0 5 100000 ? 6 0 50000 ? 0 6 1 ? 0 6 100000 ? 7 0 50000 ? 0 7 1 ? 0 7 100000 ? 8 0 50000 ? 0 8 1 ? 0 8 100000 ? 9 0 50000 ? 0 9 1 ? 0 9 100000 ? 1...
result:
ok Correct answer
Test #7:
score: 0
Accepted
time: 36ms
memory: 3592kb
input:
500 FIRST FIRST FIRST SECOND FIRST FIRST FIRST FIRST FIRST SECOND FIRST FIRST SECOND FIRST FIRST SECOND FIRST FIRST SECOND FIRST FIRST SECOND FIRST FIRST SECOND FIRST FIRST SECOND FIRST FIRST SECOND FIRST FIRST SECOND FIRST FIRST FIRST FIRST FIRST SECOND FIRST FIRST SECOND FIRST FIRST SECOND FIRST F...
output:
? 1 0 50000 ? 1 0 1 ? 1 0 100000 ? 2 1 50000 ? 1 2 1 ? 1 2 100000 ? 3 1 50000 ? 3 1 1 ? 3 1 100000 ? 4 3 50000 ? 3 4 1 ? 3 4 100000 ? 5 3 50000 ? 3 5 1 ? 3 5 100000 ? 6 3 50000 ? 3 6 1 ? 3 6 100000 ? 7 3 50000 ? 3 7 1 ? 3 7 100000 ? 8 3 50000 ? 3 8 1 ? 3 8 100000 ? 9 3 50000 ? 3 9 1 ? 3 9 100000 ? 1...
result:
ok Correct answer
Test #8:
score: 0
Accepted
time: 11ms
memory: 3544kb
input:
500 SECOND FIRST FIRST SECOND FIRST FIRST SECOND FIRST FIRST SECOND FIRST FIRST SECOND FIRST FIRST SECOND FIRST FIRST SECOND FIRST FIRST SECOND FIRST FIRST SECOND FIRST FIRST SECOND FIRST FIRST SECOND FIRST FIRST SECOND FIRST FIRST SECOND FIRST FIRST SECOND FIRST FIRST SECOND FIRST FIRST SECOND FIRS...
output:
? 1 0 50000 ? 0 1 1 ? 0 1 100000 ? 2 0 50000 ? 0 2 1 ? 0 2 100000 ? 3 0 50000 ? 0 3 1 ? 0 3 100000 ? 4 0 50000 ? 0 4 1 ? 0 4 100000 ? 5 0 50000 ? 0 5 1 ? 0 5 100000 ? 6 0 50000 ? 0 6 1 ? 0 6 100000 ? 7 0 50000 ? 0 7 1 ? 0 7 100000 ? 8 0 50000 ? 0 8 1 ? 0 8 100000 ? 9 0 50000 ? 0 9 1 ? 0 9 100000 ? 1...
result:
ok Correct answer
Test #9:
score: 0
Accepted
time: 14ms
memory: 3548kb
input:
2 FIRST SECOND QUESTION 64500 QUESTION 22602 FIRST QUESTION 37446 FIRST QUESTION 97972 QUESTION 78630 QUESTION 75591 QUESTION 63328 QUESTION 64746 QUESTION 94532 QUESTION 51275 QUESTION 12189 FIRST QUESTION 64341 QUESTION 85825 QUESTION 63713 QUESTION 36778 FIRST QUESTION 27116 FIRST QUESTION 18630 ...
output:
? 1 0 50000 ? 1 0 1 ! ! 1 ? 1 0 22602 ! 1 ? 1 0 37446 ! 1 ! 1 ! 1 ! 1 ! 1 ! 1 ! 1 ! 1 ? 1 0 12189 ! 1 ! 1 ! 1 ! 1 ? 1 0 36778 ! 1 ? 1 0 27116 ! 1 ? 1 0 18630 ! 1 ! 1 ? 1 0 28074 ! 1 ! 1 ! 1 ? 1 0 39195 ! 1 ! 1 ? 1 0 1182 ! 1 ! 1 ! 1 ! 1 ? 1 0 7017 ! 1 ? 1 0 13589 ! 1 ! 1 ! 1 ? 1 0 48324 ! 1 ! 1 ! 1 ...
result:
ok Correct answer
Test #10:
score: 0
Accepted
time: 19ms
memory: 3548kb
input:
2 FIRST SECOND QUESTION 54311 QUESTION 8466 SECOND QUESTION 82055 QUESTION 65419 QUESTION 5271 SECOND QUESTION 4799 SECOND QUESTION 21521 FIRST QUESTION 66767 QUESTION 24897 FIRST QUESTION 69127 QUESTION 84527 QUESTION 23303 FIRST QUESTION 88924 QUESTION 56421 QUESTION 88108 QUESTION 74033 QUESTION ...
output:
? 1 0 50000 ? 1 0 1 ! ! 1 ? 1 0 8466 ! 0 ! 1 ! 1 ? 1 0 5271 ! 0 ? 1 0 4799 ! 0 ? 1 0 21521 ! 1 ! 1 ? 1 0 24897 ! 1 ! 1 ! 1 ? 1 0 23303 ! 1 ! 1 ! 1 ! 1 ! 1 ? 1 0 25348 ! 1 ? 1 0 10105 ! 0 ! 1 ? 1 0 33359 ! 1 ? 1 0 49782 ! 1 ? 1 0 20392 ! 1 ! 1 ! 1 ? 1 0 4246 ! 0 ! 1 ? 1 0 8620 ! 0 ? 1 0 30435 ! 1 ? 1...
result:
ok Correct answer
Test #11:
score: 0
Accepted
time: 131ms
memory: 3564kb
input:
500 SECOND SECOND FIRST SECOND FIRST SECOND SECOND SECOND FIRST SECOND FIRST SECOND FIRST SECOND FIRST SECOND FIRST SECOND FIRST SECOND SECOND SECOND FIRST SECOND FIRST SECOND FIRST SECOND FIRST SECOND SECOND SECOND SECOND SECOND SECOND SECOND SECOND SECOND SECOND SECOND FIRST SECOND SECOND SECOND F...
output:
? 1 0 50000 ? 0 1 1 ? 2 0 50000 ? 2 0 1 ? 0 1 25000 ? 0 1 1 ? 3 2 50000 ? 2 3 1 ? 3 0 25000 ? 3 0 1 ? 0 1 12500 ? 0 1 1 ? 4 2 50000 ? 4 2 1 ? 2 3 25000 ? 2 3 1 ? 3 0 12500 ? 3 0 1 ? 0 1 6250 ? 0 1 1 ? 5 4 50000 ? 4 5 1 ? 5 2 25000 ? 5 2 1 ? 2 3 12500 ? 2 3 1 ? 3 0 6250 ? 3 0 1 ? 0 1 3125 ? 0 1 1 ? 6...
result:
ok Correct answer
Test #12:
score: 0
Accepted
time: 113ms
memory: 3520kb
input:
500 FIRST SECOND FIRST SECOND FIRST SECOND SECOND SECOND FIRST SECOND FIRST SECOND SECOND SECOND SECOND SECOND FIRST FIRST SECOND SECOND SECOND SECOND SECOND SECOND FIRST SECOND FIRST FIRST SECOND SECOND SECOND SECOND SECOND SECOND SECOND SECOND SECOND SECOND SECOND SECOND SECOND FIRST FIRST SECOND ...
output:
? 1 0 50000 ? 1 0 1 ? 2 1 50000 ? 2 1 1 ? 1 0 25000 ? 1 0 1 ? 3 2 50000 ? 2 3 1 ? 3 1 25000 ? 3 1 1 ? 1 0 12500 ? 1 0 1 ? 4 2 50000 ? 2 4 1 ? 4 3 25000 ? 3 4 1 ? 4 1 12500 ? 4 1 1 ? 4 1 25000 ? 5 2 50000 ? 2 5 1 ? 5 3 25000 ? 3 5 1 ? 5 4 12500 ? 4 5 1 ? 4 5 25000 ? 5 1 18750 ? 5 1 12501 ? 5 1 25000 ...
result:
ok Correct answer
Test #13:
score: 0
Accepted
time: 81ms
memory: 3528kb
input:
500 FIRST SECOND FIRST SECOND FIRST SECOND SECOND SECOND SECOND SECOND FIRST SECOND SECOND SECOND SECOND SECOND SECOND SECOND FIRST SECOND SECOND SECOND SECOND SECOND SECOND SECOND SECOND SECOND SECOND SECOND SECOND SECOND SECOND SECOND SECOND SECOND SECOND SECOND SECOND SECOND FIRST SECOND SECOND S...
output:
? 1 0 50000 ? 1 0 1 ? 2 1 50000 ? 2 1 1 ? 1 0 25000 ? 1 0 1 ? 3 2 50000 ? 2 3 1 ? 3 1 25000 ? 1 3 1 ? 3 0 12500 ? 3 0 1 ? 4 2 50000 ? 2 4 1 ? 4 1 25000 ? 1 4 1 ? 4 3 12500 ? 3 4 1 ? 4 0 6250 ? 4 0 1 ? 5 2 50000 ? 2 5 1 ? 5 1 25000 ? 1 5 1 ? 5 3 12500 ? 3 5 1 ? 5 4 6250 ? 4 5 1 ? 5 0 3125 ? 0 5 1 ? 6...
result:
ok Correct answer
Test #14:
score: 0
Accepted
time: 120ms
memory: 3616kb
input:
500 FIRST SECOND SECOND SECOND FIRST SECOND SECOND FIRST SECOND SECOND SECOND SECOND SECOND FIRST SECOND SECOND SECOND SECOND SECOND SECOND FIRST SECOND SECOND SECOND SECOND SECOND SECOND FIRST SECOND SECOND SECOND FIRST SECOND SECOND FIRST SECOND SECOND SECOND SECOND SECOND SECOND SECOND FIRST SECO...
output:
? 1 0 50000 ? 1 0 1 ? 2 1 50000 ? 1 2 1 ? 2 0 25000 ? 2 0 1 ? 3 1 50000 ? 1 3 1 ? 1 3 100000 ? 4 1 50000 ? 1 4 1 ? 4 2 25000 ? 2 4 1 ? 4 0 12500 ? 4 0 1 ? 5 1 50000 ? 1 5 1 ? 5 2 25000 ? 2 5 1 ? 5 4 12500 ? 4 5 1 ? 4 5 25000 ? 6 1 50000 ? 1 6 1 ? 6 2 25000 ? 2 6 1 ? 6 4 12500 ? 4 6 1 ? 4 6 25000 ? 6...
result:
ok Correct answer
Test #15:
score: 0
Accepted
time: 148ms
memory: 3560kb
input:
500 FIRST SECOND FIRST SECOND FIRST SECOND SECOND SECOND SECOND SECOND FIRST SECOND SECOND SECOND SECOND SECOND FIRST SECOND FIRST SECOND SECOND SECOND SECOND SECOND FIRST SECOND FIRST SECOND SECOND FIRST SECOND SECOND SECOND SECOND SECOND SECOND SECOND SECOND FIRST SECOND SECOND SECOND SECOND SECON...
output:
? 1 0 50000 ? 1 0 1 ? 2 1 50000 ? 2 1 1 ? 1 0 25000 ? 1 0 1 ? 3 2 50000 ? 2 3 1 ? 3 1 25000 ? 1 3 1 ? 3 0 12500 ? 3 0 1 ? 4 2 50000 ? 2 4 1 ? 4 1 25000 ? 1 4 1 ? 4 3 12500 ? 4 3 1 ? 3 0 6250 ? 3 0 1 ? 5 2 50000 ? 2 5 1 ? 5 1 25000 ? 1 5 1 ? 5 4 12500 ? 5 4 1 ? 4 3 6250 ? 4 3 1 ? 3 0 3125 ? 0 3 1 ? 0...
result:
ok Correct answer
Test #16:
score: 0
Accepted
time: 80ms
memory: 3664kb
input:
500 FIRST SECOND SECOND SECOND SECOND SECOND SECOND SECOND SECOND SECOND FIRST SECOND SECOND SECOND SECOND SECOND SECOND SECOND FIRST SECOND SECOND SECOND SECOND SECOND SECOND SECOND FIRST FIRST SECOND SECOND SECOND FIRST SECOND FIRST SECOND SECOND FIRST SECOND FIRST SECOND SECOND SECOND SECOND SECO...
output:
? 1 0 50000 ? 1 0 1 ? 2 1 50000 ? 1 2 1 ? 2 0 25000 ? 0 2 1 ? 3 1 50000 ? 1 3 1 ? 3 0 25000 ? 0 3 1 ? 3 2 12500 ? 3 2 1 ? 4 1 50000 ? 1 4 1 ? 4 0 25000 ? 0 4 1 ? 4 3 12500 ? 3 4 1 ? 4 2 6250 ? 4 2 1 ? 5 1 50000 ? 1 5 1 ? 5 0 25000 ? 0 5 1 ? 5 3 12500 ? 3 5 1 ? 5 4 6250 ? 5 4 1 ? 5 4 12500 ? 6 1 5000...
result:
ok Correct answer