QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #832310 | #866. Display of Springs | cwfxlh | RE | 1ms | 4036kb | C++14 | 1.0kb | 2024-12-25 20:24:38 | 2024-12-25 20:24:40 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int n,mxv[500003],lf[100003],w,ans;
string s;
int Query(int a,int b,int W){
cout<<"? "<<a-1<<' '<<b-1<<' '<<W<<'\n';
fflush(stdout);
cin>>s;
if(s[0]=='F')return 1;
if(s[0]=='S')return 2;
return 0;
}
void build(int now,int l,int r){
if(l==r){lf[l]=now;return;}
build(now*2,l,((l+r)>>1));
build(now*2+1,((l+r)>>1)+1,r);
return;
}
void add(int now,int l,int r,int val){
if(mxv[now]&&Query(mxv[now],val,((l+r)/2))==2)swap(mxv[now],val);
if(!mxv[now]){swap(mxv[now],val);return;}
if(Query(mxv[now],val,l)==2)add(now*2,l,((l+r)>>1),val);
else add(now*2+1,((l+r)>>1)+1,r,val);
return;
}
int main(){
cin>>n;
build(1,1,100000);
for(int i=1;i<=n;i++)add(1,1,100000,i);
cout<<"!\n";
fflush(stdout);
while(1){
cin>>s;
if(s[0]=='F')break;
cin>>w;
ans=0;
for(int i=lf[w];i;i/=2){
if(ans==0)ans=mxv[i];
else if(mxv[i]&&Query(ans,mxv[i],w)==2)ans=mxv[i];
}
cout<<"! "<<ans-1<<'\n';
fflush(stdout);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3960kb
input:
3 SECOND FIRST SECOND SECOND QUESTION 2 FIRST QUESTION 6 SECOND FINISH
output:
? 0 1 50000 ? 1 0 1 ? 1 2 50000 ? 2 1 1 ! ? 1 2 2 ! 1 ? 1 2 6 ! 2
result:
ok Correct answer
Test #2:
score: 0
Accepted
time: 1ms
memory: 4036kb
input:
6 SECOND EQUAL SECOND SECOND SECOND SECOND SECOND SECOND SECOND SECOND SECOND SECOND SECOND SECOND SECOND SECOND SECOND SECOND SECOND SECOND SECOND SECOND QUESTION 1 FIRST FIRST FIRST FIRST QUESTION 2 EQUAL FIRST FIRST FIRST QUESTION 3 SECOND EQUAL FIRST FIRST QUESTION 4 SECOND SECOND EQUAL FIRST QU...
output:
? 0 1 50000 ? 1 0 1 ? 1 2 50000 ? 2 1 1 ? 2 3 50000 ? 3 2 1 ? 1 2 25000 ? 2 1 1 ? 3 4 50000 ? 4 3 1 ? 2 3 25000 ? 3 2 1 ? 1 2 12500 ? 2 1 1 ? 4 5 50000 ? 5 4 1 ? 3 4 25000 ? 4 3 1 ? 2 3 12500 ? 3 2 1 ? 1 2 6250 ? 2 1 1 ! ? 1 2 1 ? 1 3 1 ? 1 4 1 ? 1 5 1 ! 1 ? 1 2 2 ? 1 3 2 ? 1 4 2 ? 1 5 2 ! 1 ? 1 2 3...
result:
ok Correct answer
Test #3:
score: -100
Runtime Error
input:
326 FIRST FIRST FIRST SECOND SECOND SECOND SECOND SECOND FIRST SECOND FIRST SECOND SECOND FIRST FIRST FIRST FIRST FIRST FIRST SECOND FIRST FIRST FIRST SECOND FIRST FIRST FIRST FIRST SECOND FIRST SECOND FIRST SECOND FIRST FIRST FIRST FIRST FIRST SECOND FIRST SECOND FIRST FIRST FIRST SECOND FIRST SECO...
output:
? 0 1 50000 ? 0 1 1 ? 0 2 50000 ? 0 2 1 ? 0 3 50000 ? 3 0 1 ? 2 0 25000 ? 0 2 1 ? 3 4 50000 ? 3 4 1 ? 0 4 25000 ? 0 4 1 ? 2 4 12500 ? 4 2 1 ? 3 5 50000 ? 3 5 1 ? 1 5 75000 ? 1 5 50001 ? 3 6 50000 ? 3 6 1 ? 0 6 25000 ? 0 6 1 ? 3 7 50000 ? 3 7 1 ? 0 7 25000 ? 0 7 1 ? 6 7 37500 ? 6 7 25001 ? 3 8 50000 ...