QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#203806#866. Display of SpringsZhou_JKAC ✓27ms3600kbC++231.7kb2023-10-06 20:39:472023-10-06 20:39:48

Judging History

你现在查看的是最新测评结果

  • [2023-10-06 20:39:48]
  • 评测
  • 测评结果:AC
  • 用时:27ms
  • 内存:3600kb
  • [2023-10-06 20:39:47]
  • 提交

answer

#include<iostream>
#include<cstdio>
using namespace std;
const int M=100005;
int n,m;
string query(int a,int b,int w)
{
    a--,b--;
    cout<<"? "<<a<<" "<<b<<" "<<w<<endl;
    string str;
    cin>>str;
    return str;
}
struct Segment_Tree
{
    #define ls i*2
    #define rs i*2+1
    struct Node
    {
        int tag;
    }tree[M*4];
    void insert(int i,int l,int r,int u)
    {
        if(!tree[i].tag)
        {
            tree[i].tag=u;
            return;
        }
        if(::query(tree[i].tag,u,l)=="SECOND") swap(u,tree[i].tag);
        if(l==r) return;
        int mid=(l+r)/2;
        if(::query(tree[i].tag,u,mid)=="SECOND") insert(ls,l,mid,tree[i].tag),tree[i].tag=u;
        else insert(rs,mid+1,r,u);
        return;
    }
    int query(int i,int l,int r,int u)
    {
        if(l==r) return tree[i].tag;
        int mid=(l+r)/2;
        int p=0;
        if(u<=mid) p=query(ls,l,mid,u);
        else p=query(rs,mid+1,r,u);
        if(!p) return tree[i].tag;
        if(!tree[i].tag) return p;
        if(::query(tree[i].tag,p,u)=="SECOND") return p;
        else return tree[i].tag;
    }
    #undef ls
    #undef rs
}T;
int solve(int w)
{
    return T.query(1,1,m,w);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    cin>>n;
    m=100000;
    for(int i=1;i<=n;i++)
        T.insert(1,1,m,i);
    cout<<"!"<<endl;
    while(true)
    {
        string str;
        cin>>str;
        if(str=="QUESTION")
        {
            int w;
            cin>>w;
            int res=solve(w);
            cout<<"! "<<res-1<<endl;
        }
        else break;
    }
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3488kb

input:

3
SECOND
FIRST
FIRST
SECOND
QUESTION 2
SECOND
QUESTION 6
FIRST
FINISH

output:

? 0 1 1
? 1 0 50000
? 1 2 1
? 1 2 50000
!
? 2 1 2
! 1
? 2 1 6
! 2

result:

ok Correct answer

Test #2:

score: 0
Accepted
time: 1ms
memory: 3448kb

input:

6
EQUAL
SECOND
FIRST
SECOND
EQUAL
SECOND
FIRST
SECOND
FIRST
SECOND
EQUAL
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
EQUAL
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
EQUAL
SECOND
QUESTION 1
EQUAL
SECOND
SECOND
SECOND
SECOND
QUESTION 2
FIRST
EQUAL
SECOND
SECOND
SECOND
QUESTION 3
FIR...

output:

? 0 1 1
? 0 1 50000
? 1 2 1
? 1 2 50000
? 0 1 1
? 0 1 25000
? 2 3 1
? 2 3 50000
? 1 2 1
? 1 2 25000
? 0 1 1
? 0 1 12500
? 3 4 1
? 3 4 50000
? 2 3 1
? 2 3 25000
? 1 2 1
? 1 2 12500
? 0 1 1
? 0 1 6250
? 4 5 1
? 4 5 50000
? 3 4 1
? 3 4 25000
? 2 3 1
? 2 3 12500
? 1 2 1
? 1 2 6250
? 0 1 1
? 0 1 3125
!
?...

result:

ok Correct answer

Test #3:

score: 0
Accepted
time: 13ms
memory: 3600kb

input:

326
FIRST
FIRST
SECOND
SECOND
FIRST
SECOND
FIRST
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
FIRST
FIRST
FIRST
FIRST
FIRST
SECOND
SECOND
FIRST
FIRST
SECOND
SECOND
FIRST
FIRST
FIRST
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST
FIRST
FIRST
FIRST
FIRST
SECOND
FIRST
SECOND
FIRST
FIRST
FIRST
SECOND
FIRST
S...

output:

? 0 1 1
? 0 1 50000
? 0 2 1
? 2 0 50000
? 0 3 1
? 0 3 50000
? 2 0 1
? 2 0 25000
? 3 4 1
? 4 3 50000
? 0 4 1
? 4 0 25000
? 2 4 1
? 4 2 12500
? 3 5 1
? 3 5 50000
? 1 5 50001
? 1 5 75000
? 3 6 1
? 6 3 50000
? 0 6 1
? 0 6 25000
? 3 7 1
? 7 3 50000
? 0 7 1
? 0 7 25000
? 6 7 25001
? 6 7 37500
? 3 8 1
? 8 ...

result:

ok Correct answer

Test #4:

score: 0
Accepted
time: 0ms
memory: 3452kb

input:

19
SECOND
FIRST
FIRST
FIRST
SECOND
FIRST
FIRST
FIRST
SECOND
FIRST
SECOND
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
SECOND
FIRST
SECOND
FIRST
FIRST
SECOND
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST...

output:

? 0 1 1
? 1 0 50000
? 1 2 1
? 1 2 50000
? 0 2 50001
? 2 0 75000
? 1 3 1
? 1 3 50000
? 2 3 50001
? 3 2 75000
? 0 2 75001
? 2 0 87500
? 1 4 1
? 1 4 50000
? 3 4 50001
? 3 4 75000
? 2 4 75001
? 2 4 87500
? 0 4 87501
? 0 4 93750
? 1 5 1
? 1 5 50000
? 3 5 50001
? 3 5 75000
? 2 5 75001
? 2 5 87500
? 0 5 87...

result:

ok Correct answer

Test #5:

score: 0
Accepted
time: 10ms
memory: 3512kb

input:

500
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
SECOND
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
SECOND
FIRST
SECOND
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND...

output:

? 0 1 1
? 1 0 50000
? 1 2 1
? 2 1 50000
? 0 1 50001
? 1 0 75000
? 2 3 1
? 3 2 50000
? 1 2 50001
? 2 1 75000
? 0 1 75001
? 1 0 87500
? 3 4 1
? 3 4 50000
? 2 4 50001
? 2 4 75000
? 1 4 75001
? 1 4 87500
? 0 4 87501
? 4 0 93750
? 3 5 1
? 3 5 50000
? 2 5 50001
? 2 5 75000
? 1 5 75001
? 1 5 87500
? 4 5 87...

result:

ok Correct answer

Test #6:

score: 0
Accepted
time: 19ms
memory: 3576kb

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:

? 0 1 1
? 0 1 50000
? 0 2 1
? 0 2 50000
? 1 2 50001
? 1 2 75000
? 0 3 1
? 0 3 50000
? 1 3 50001
? 1 3 75000
? 2 3 75001
? 2 3 87500
? 0 4 1
? 0 4 50000
? 1 4 50001
? 1 4 75000
? 2 4 75001
? 2 4 87500
? 3 4 87501
? 3 4 93750
? 0 5 1
? 0 5 50000
? 1 5 50001
? 1 5 75000
? 2 5 75001
? 2 5 87500
? 3 5 87...

result:

ok Correct answer

Test #7:

score: 0
Accepted
time: 24ms
memory: 3548kb

input:

500
SECOND
FIRST
FIRST
FIRST
FIRST
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
SECOND
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
SECOND
FIRST
SECOND
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
FIRS...

output:

? 0 1 1
? 1 0 50000
? 1 2 1
? 1 2 50000
? 0 2 50001
? 0 2 75000
? 1 3 1
? 3 1 50000
? 0 1 50001
? 1 0 75000
? 2 0 75001
? 0 2 87500
? 3 4 1
? 3 4 50000
? 1 4 50001
? 1 4 75000
? 0 4 75001
? 0 4 87500
? 2 4 87501
? 4 2 93750
? 3 5 1
? 3 5 50000
? 1 5 50001
? 1 5 75000
? 0 5 75001
? 0 5 87500
? 4 5 87...

result:

ok Correct answer

Test #8:

score: 0
Accepted
time: 19ms
memory: 3588kb

input:

500
FIRST
FIRST
FIRST
FIRST
SECOND
FIRST
FIRST
FIRST
FIRST
FIRST
SECOND
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
SECOND
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
SECOND
FIRST
SECOND
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
...

output:

? 0 1 1
? 0 1 50000
? 0 2 1
? 0 2 50000
? 1 2 50001
? 2 1 75000
? 0 3 1
? 0 3 50000
? 2 3 50001
? 2 3 75000
? 1 3 75001
? 3 1 87500
? 0 4 1
? 0 4 50000
? 2 4 50001
? 2 4 75000
? 3 4 75001
? 3 4 87500
? 1 4 87501
? 4 1 93750
? 0 5 1
? 0 5 50000
? 2 5 50001
? 2 5 75000
? 3 5 75001
? 3 5 87500
? 4 5 87...

result:

ok Correct answer

Test #9:

score: 0
Accepted
time: 2ms
memory: 3488kb

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:

? 0 1 1
? 0 1 50000
!
! 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: 0ms
memory: 3432kb

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:

? 0 1 1
? 0 1 50000
!
! 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: 17ms
memory: 3516kb

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:

? 0 1 1
? 1 0 50000
? 0 2 1
? 0 2 50000
? 1 0 1
? 1 0 25000
? 2 3 1
? 3 2 50000
? 0 3 1
? 0 3 25000
? 1 0 1
? 1 0 12500
? 2 4 1
? 2 4 50000
? 3 2 1
? 3 2 25000
? 0 3 1
? 0 3 12500
? 1 0 1
? 1 0 6250
? 4 5 1
? 5 4 50000
? 2 5 1
? 2 5 25000
? 3 2 1
? 3 2 12500
? 0 3 1
? 0 3 6250
? 1 0 1
? 1 0 3125
? 4...

result:

ok Correct answer

Test #12:

score: 0
Accepted
time: 18ms
memory: 3448kb

input:

500
FIRST
SECOND
FIRST
SECOND
FIRST
SECOND
SECOND
SECOND
FIRST
SECOND
FIRST
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
FIRST
SECOND
SECOND
SECOND
SECOND
FIRST
FIRST
SECOND
FIRST
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
FIRST
SECOND
FIRST
SECOND
SECOND...

output:

? 0 1 1
? 0 1 50000
? 1 2 1
? 1 2 50000
? 0 1 1
? 0 1 25000
? 2 3 1
? 3 2 50000
? 1 3 1
? 1 3 25000
? 0 1 1
? 0 1 12500
? 2 4 1
? 4 2 50000
? 3 4 1
? 4 3 25000
? 1 4 1
? 4 1 12500
? 2 5 1
? 5 2 50000
? 3 5 1
? 5 3 25000
? 4 5 1
? 4 5 12500
? 1 5 12501
? 5 1 18750
? 2 6 1
? 6 2 50000
? 3 6 1
? 6 3 25...

result:

ok Correct answer

Test #13:

score: 0
Accepted
time: 7ms
memory: 3512kb

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:

? 0 1 1
? 0 1 50000
? 1 2 1
? 1 2 50000
? 0 1 1
? 0 1 25000
? 2 3 1
? 3 2 50000
? 1 3 1
? 3 1 25000
? 0 3 1
? 0 3 12500
? 2 4 1
? 4 2 50000
? 1 4 1
? 4 1 25000
? 3 4 1
? 4 3 12500
? 0 4 1
? 0 4 6250
? 2 5 1
? 5 2 50000
? 1 5 1
? 5 1 25000
? 3 5 1
? 5 3 12500
? 4 5 1
? 5 4 6250
? 0 5 1
? 5 0 3125
? 2...

result:

ok Correct answer

Test #14:

score: 0
Accepted
time: 17ms
memory: 3516kb

input:

500
FIRST
SECOND
SECOND
SECOND
FIRST
SECOND
FIRST
FIRST
SECOND
SECOND
SECOND
SECOND
FIRST
SECOND
SECOND
SECOND
SECOND
SECOND
FIRST
FIRST
SECOND
SECOND
SECOND
SECOND
FIRST
FIRST
SECOND
SECOND
FIRST
SECOND
FIRST
FIRST
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
FIRST
SECOND
SECOND
SECOND
FIRST
FIRST
SEC...

output:

? 0 1 1
? 0 1 50000
? 1 2 1
? 2 1 50000
? 0 2 1
? 0 2 25000
? 1 3 1
? 1 3 50000
? 1 4 1
? 4 1 50000
? 2 4 1
? 4 2 25000
? 0 4 1
? 0 4 12500
? 1 5 1
? 5 1 50000
? 2 5 1
? 5 2 25000
? 4 5 1
? 4 5 12500
? 1 6 1
? 6 1 50000
? 2 6 1
? 6 2 25000
? 4 6 1
? 4 6 12500
? 5 6 12501
? 6 5 18750
? 1 7 1
? 1 7 50...

result:

ok Correct answer

Test #15:

score: 0
Accepted
time: 27ms
memory: 3452kb

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
FIRST
FIRST
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
FIRST
FIRST
SECOND
SECOND
SECOND
SECOND
FIRST
SECOND
F...

output:

? 0 1 1
? 0 1 50000
? 1 2 1
? 1 2 50000
? 0 1 1
? 0 1 25000
? 2 3 1
? 3 2 50000
? 1 3 1
? 3 1 25000
? 0 3 1
? 0 3 12500
? 2 4 1
? 4 2 50000
? 1 4 1
? 4 1 25000
? 3 4 1
? 3 4 12500
? 0 3 1
? 0 3 6250
? 2 5 1
? 5 2 50000
? 1 5 1
? 5 1 25000
? 4 5 1
? 4 5 12500
? 3 4 1
? 3 4 6250
? 0 3 1
? 0 3 3125
? 2...

result:

ok Correct answer

Test #16:

score: 0
Accepted
time: 9ms
memory: 3556kb

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
SECOND
FIRST
SECOND
SECOND
FIRST
SECOND
FIRST
SECOND
FIRST
FIRST
FIRST
SECOND
SECOND
SECOND
SECOND
SECOND
SECOND
SECO...

output:

? 0 1 1
? 0 1 50000
? 1 2 1
? 2 1 50000
? 0 2 1
? 2 0 25000
? 1 3 1
? 3 1 50000
? 0 3 1
? 3 0 25000
? 2 3 1
? 2 3 12500
? 1 4 1
? 4 1 50000
? 0 4 1
? 4 0 25000
? 3 4 1
? 4 3 12500
? 2 4 1
? 2 4 6250
? 1 5 1
? 5 1 50000
? 0 5 1
? 5 0 25000
? 3 5 1
? 5 3 12500
? 4 5 1
? 5 4 6250
? 1 6 1
? 6 1 50000
? ...

result:

ok Correct answer