QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#876170#9734. Identify ChordLuluTL 9ms3712kbC++142.5kb2025-01-30 18:00:032025-01-30 18:00:03

Judging History

This is the latest submission verdict.

  • [2025-01-30 18:00:03]
  • Judged
  • Verdict: TL
  • Time: 9ms
  • Memory: 3712kb
Show
  • [2025-01-30 18:00:03]
  • Submitted

answer

/*
Author:
Homework:QH01
Problem:identify
Time:2025 - 1 - 30
Calm down!
Think twice and type.
*/
#include<bits/stdc++.h>
#define REP(i,l,r) for(int i=(l);i<=(r);i++)
#define PER(i,r,l) for(int i=(r);i>=(l);i--)
#define pi pair<int,int>
#define mkp(x,y) make_pair(x,y)
#define fi first
#define se second
#define ll long long
#define lc tr[i].ch[0]
#define rc tr[i].ch[1]
#define Lc tr[j].ch[0]
#define Rc tr[j].ch[1]
#define lowbit(i) (i&(-i))
using namespace std;
inline int read(){
    int x=0,f=1;
    char c=getchar();
    while(!isdigit(c)){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(isdigit(c)){
        x=(x<<3)+(x<<1)+c-'0';
        c=getchar();
    }
    return x*f;
}
void write(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
int getrand(int mod){
    ll x=0;
    x<<=15,x+=rand();
    x<<=15,x+=rand();
    x<<=15,x+=rand();
    return x%mod+1;
}
int cnt;
int query(int x,int y){
    if(++cnt>40)exit(0);
    putchar('?'),putchar(' ');
    write(x),putchar(' ');
    write(y),putchar('\n');
    fflush(stdout);
    return read();
}
void print(int x,int y){
    putchar('!'),putchar(' ');
    write(x),putchar(' ');
    write(y),putchar('\n');
    fflush(stdout);
    int res=read();
    if(res==-1)exit(0);
}
int n,ans;
bool check(int x,int y){
    if(y<x)swap(x,y);
    int dis=min(y-x,x+n-y);
    ans=query(x,y);
    return ans!=dis;
}
void solve(){
    cnt=0;
    n=read();
    int x=getrand(n),y=x+n/2;if(y>n)y-=n;
    while(!check(x,y)){
        x=getrand(n),y=x+n/2;
        if(y>n)y-=n;
    }
    if(x>y)swap(x,y);
    bool dirx=0,diry=0;
    if(query(x%n+1,y)==ans-1)dirx=1;
    if(query(x,y%n+1)==ans-1)diry=1;
    if(dirx){
        int l=x+1,r=y-1,res=x;
        while(l<=r){
            int mid=(l+r)/2;
            if(query(mid,y)==ans-(mid-x))res=mid,l=mid+1;
            else r=mid-1;
        }
        ans-=res-x+1,x=res;
    }else{
        int l=y+1,r=n+x-1,res=n+x;
        while(l<=r){
            int mid=(l+r)/2;int v=mid;if(v>n)v-=n;
            if(query(v,y)==ans-(n+x-mid))res=mid,r=mid-1;
            else l=mid+1;
        }
        ans-=(n+x)-res+1,x=res;
    }
    if(diry)y+=ans;
    else y+=n-ans;
    if(x>n)x-=n;
    if(y>n)y-=n;
    print(x,y);
}
int main(){
    srand(time(0));
    // freopen("identify.in","r",stdin);
    // freopen("identify.out","w",stdout);
    int T=read();
    while(T--)solve();
    return 0;
}
源文件, 语言: C++14

詳細信息

Test #1:

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

input:

2
6
2
2
2
1
2
1
4
2
2
1
1
1
1
1

output:

? 2 5
? 3 5
? 2 6
? 6 5
? 1 5
! 2 4
? 2 4
? 2 4
? 1 3
? 2 3
? 1 4
? 4 3
! 1 3

result:

ok ok (2 test cases)

Test #2:

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

input:

1000
15
5
6
6
4
6
6
1
19
3
2
2
5
3
2
1
17
3
4
4
4
4
3
2
1
15
7
7
7
6
7
5
3
4
4
1
14
7
5
6
4
3
5
4
1
15
2
1
3
4
2
1
1
17
7
8
7
4
5
4
1
20
6
7
5
5
7
8
7
1
13
2
3
3
3
4
3
1
18
5
6
6
4
2
3
1
13
6
4
5
3
3
2
3
1
14
4
3
3
3
3
2
1
17
5
4
6
5
5
4
1
12
3
2
2
3
2
3
1
10
5
3
2
4
1
2
1
14
6
5
6
3
2
2
1
19
7
6
8
...

output:

? 5 12
? 6 12
? 5 13
? 1 12
? 3 12
? 4 12
! 5 8
? 2 11
? 3 11
? 2 12
? 6 11
? 4 11
? 3 11
! 3 12
? 4 12
? 5 12
? 4 13
? 16 12
? 1 12
? 2 12
? 3 12
! 3 11
? 8 15
? 8 15
? 7 14
? 5 13
? 6 13
? 5 14
? 1 13
? 3 13
? 2 13
! 3 1
? 3 10
? 6 13
? 7 13
? 6 14
? 2 13
? 4 13
? 5 13
! 5 2
? 1 9
? 2 9
? 1 10
? 5...

result:

ok ok (1000 test cases)

Test #3:

score: 0
Accepted
time: 8ms
memory: 3712kb

input:

1000
21
2
3
3
5
3
2
1
1
22
8
9
9
4
5
3
1
20
5
4
6
4
3
2
3
1
22
4
3
5
3
2
1
2
1
21
7
6
6
2
3
3
1
21
8
9
7
2
2
3
3
1
24
5
4
6
5
2
3
1
22
10
9
10
5
3
5
1
21
8
9
9
5
5
5
4
1
23
10
9
9
4
3
3
2
1
21
6
7
7
5
7
6
5
1
24
11
11
11
6
9
9
1
20
10
9
8
9
5
7
6
6
1
24
11
10
11
6
8
8
1
23
9
10
8
5
6
4
1
23
3
4
2
6
...

output:

? 11 21
? 12 21
? 11 1
? 5 21
? 8 21
? 9 21
? 10 21
! 10 21
? 8 19
? 9 19
? 8 20
? 2 19
? 5 19
? 3 19
! 3 17
? 2 12
? 3 12
? 2 13
? 7 12
? 4 12
? 5 12
? 6 12
! 5 11
? 4 15
? 5 15
? 4 16
? 9 15
? 6 15
? 7 15
? 8 15
! 7 15
? 2 12
? 3 12
? 2 13
? 7 12
? 9 12
? 8 12
! 7 13
? 4 14
? 5 14
? 4 15
? 19 14
?...

result:

ok ok (1000 test cases)

Test #4:

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

input:

1000
25
11
10
10
6
9
10
10
1
25
11
12
11
6
8
7
8
1
25
12
7
8
8
3
4
2
1
25
5
4
6
6
6
4
5
1
26
12
11
12
6
4
6
1
26
9
10
10
2
3
4
3
1
26
11
12
12
4
1
1
2
1
27
12
11
13
7
10
11
11
1
25
8
7
9
6
9
7
8
1
27
9
10
8
6
7
7
6
1
27
11
12
10
4
3
5
5
1
27
13
4
3
3
7
5
3
4
1
26
9
8
8
3
4
4
1
25
9
10
8
6
9
10
10
1
...

output:

? 5 17
? 6 17
? 5 18
? 11 17
? 8 17
? 6 17
? 7 17
! 6 1
? 3 16
? 4 16
? 3 17
? 22 16
? 25 16
? 23 16
? 24 16
! 25 9
? 3 15
? 11 24
? 12 24
? 11 25
? 5 24
? 8 24
? 6 24
! 6 23
? 2 14
? 3 14
? 2 15
? 8 14
? 5 14
? 3 14
? 4 14
! 3 11
? 12 25
? 13 25
? 12 26
? 18 25
? 21 25
? 19 25
! 18 20
? 13 26
? 14 ...

result:

ok ok (1000 test cases)

Test #5:

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

input:

1000
29
6
7
5
7
6
4
5
1
28
14
11
10
10
7
8
8
7
1
30
7
6
6
8
4
6
5
1
29
5
6
6
7
9
7
6
1
28
6
5
7
3
3
1
2
1
29
1
2
2
7
5
3
2
1
29
9
10
8
7
5
7
6
1
28
11
10
12
7
8
9
9
1
30
6
7
7
6
2
4
3
1
30
6
5
7
8
7
5
6
1
28
9
8
10
7
6
8
7
1
29
14
14
13
12
14
6
3
1
1
1
29
11
10
12
7
11
10
11
1
29
7
6
8
8
4
6
5
1
29
...

output:

? 5 19
? 6 19
? 5 20
? 26 19
? 1 19
? 3 19
? 2 19
! 3 22
? 2 16
? 4 18
? 5 18
? 4 19
? 11 18
? 7 18
? 9 18
? 8 18
! 8 24
? 14 29
? 15 29
? 14 30
? 21 29
? 17 29
? 19 29
? 18 29
! 17 2
? 2 17
? 3 17
? 2 18
? 24 17
? 27 17
? 29 17
? 1 17
! 2 13
? 9 23
? 10 23
? 9 24
? 16 23
? 12 23
? 14 23
? 15 23
! 1...

result:

ok ok (1000 test cases)

Test #6:

score: 0
Accepted
time: 4ms
memory: 3584kb

input:

1000
32
13
12
14
8
9
10
10
1
30
14
14
13
7
11
12
11
1
32
10
11
11
8
6
6
5
1
31
14
13
13
8
11
10
10
1
32
5
6
6
7
3
3
2
1
32
16
6
7
5
6
2
4
3
1
31
9
8
10
6
6
4
5
1
31
15
15
5
6
6
5
1
3
2
1
32
16
12
11
13
8
8
8
7
1
30
14
14
13
6
3
5
6
1
31
10
11
11
4
6
4
3
1
31
15
11
10
10
4
4
2
3
1
33
16
7
8
6
8
9
7
6...

output:

? 1 17
? 2 17
? 1 18
? 9 17
? 5 17
? 7 17
? 6 17
! 5 9
? 1 16
? 2 16
? 1 17
? 23 16
? 27 16
? 29 16
? 28 16
! 28 26
? 14 30
? 15 30
? 14 31
? 6 30
? 10 30
? 8 30
? 9 30
! 9 26
? 11 26
? 12 26
? 11 27
? 18 26
? 14 26
? 16 26
? 15 26
! 15 4
? 6 22
? 7 22
? 6 23
? 30 22
? 2 22
? 4 22
? 3 22
! 3 21
? 13...

result:

ok ok (1000 test cases)

Test #7:

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

input:

1000
34
12
13
13
3
4
3
2
1
33
10
11
11
8
12
11
10
9
1
33
10
11
9
2
4
4
3
1
34
17
9
10
10
6
4
4
3
1
34
15
16
16
6
4
4
5
1
35
15
16
14
9
13
12
13
1
34
6
7
7
7
3
3
2
1
34
10
11
11
5
5
3
4
1
34
16
16
15
7
4
6
6
1
33
15
14
14
7
5
5
4
1
33
15
14
16
8
12
14
14
1
34
16
16
15
8
11
10
10
1
33
11
10
10
3
5
3
2...

output:

? 15 32
? 16 32
? 15 33
? 6 32
? 2 32
? 4 32
? 5 32
! 5 31
? 7 23
? 8 23
? 7 24
? 31 23
? 2 23
? 4 23
? 5 23
? 6 23
! 6 15
? 6 23
? 7 23
? 6 24
? 31 23
? 27 23
? 29 23
? 30 23
! 31 24
? 5 22
? 17 34
? 18 34
? 17 1
? 8 34
? 12 34
? 10 34
? 11 34
! 11 32
? 13 30
? 14 30
? 13 31
? 4 30
? 34 30
? 2 30
?...

result:

ok ok (1000 test cases)

Test #8:

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

input:

1000
36
17
16
17
8
4
2
2
1
36
3
4
4
8
4
2
1
1
36
17
16
16
9
14
15
15
1
36
17
16
16
9
13
11
11
1
36
9
10
10
2
4
2
1
1
36
8
7
9
9
10
8
7
1
35
17
17
12
13
13
3
3
1
2
1
36
9
8
10
2
5
3
2
1
1
36
18
6
7
7
7
3
3
2
1
36
16
15
17
9
12
10
9
8
1
36
1
2
2
9
6
4
3
2
1
36
8
7
7
9
6
6
5
1
36
17
17
17
9
13
15
16
17...

output:

? 3 21
? 4 21
? 3 22
? 12 21
? 16 21
? 18 21
? 19 21
! 18 20
? 1 19
? 2 19
? 1 20
? 28 19
? 32 19
? 34 19
? 35 19
! 35 19
? 8 26
? 9 26
? 8 27
? 17 26
? 12 26
? 10 26
? 11 26
! 10 4
? 11 29
? 12 29
? 11 30
? 20 29
? 15 29
? 17 29
? 18 29
! 17 3
? 14 32
? 15 32
? 14 33
? 5 32
? 9 32
? 7 32
? 6 32
! 6...

result:

ok ok (1000 test cases)

Test #9:

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

input:

1000
37
11
12
12
9
12
10
9
1
36
17
17
16
8
4
6
7
8
1
38
17
18
18
9
14
14
13
1
37
12
13
13
9
13
15
14
13
1
37
12
11
13
10
8
8
7
1
36
16
17
17
7
4
6
5
1
37
5
6
4
9
6
4
3
1
37
9
8
8
9
7
7
6
1
37
17
16
17
10
13
11
10
11
1
37
6
7
7
9
9
7
6
5
1
37
17
16
16
8
5
6
5
1
37
18
18
17
18
16
9
12
11
12
1
36
15
14...

output:

? 16 35
? 17 35
? 16 36
? 7 35
? 11 35
? 13 35
? 14 35
! 14 27
? 1 19
? 2 19
? 1 20
? 28 19
? 23 19
? 25 19
? 26 19
? 27 19
! 28 26
? 11 30
? 12 30
? 11 31
? 1 30
? 6 30
? 8 30
? 7 30
! 7 18
? 13 32
? 14 32
? 13 33
? 4 32
? 8 32
? 10 32
? 11 32
? 12 32
! 13 21
? 14 33
? 15 33
? 14 34
? 23 33
? 18 33...

result:

ok ok (1000 test cases)

Test #10:

score: 0
Accepted
time: 5ms
memory: 3584kb

input:

1000
39
11
10
10
3
6
4
3
2
1
38
8
7
9
7
4
4
3
1
38
13
14
14
9
14
12
11
1
39
13
14
12
9
8
7
6
1
38
15
14
16
6
5
8
7
1
39
13
12
12
8
9
7
6
7
1
39
14
15
13
4
4
5
4
3
1
38
18
17
18
9
5
8
9
1
39
13
14
12
3
4
4
3
2
1
39
12
11
13
10
9
10
9
8
1
39
19
5
6
4
10
6
4
3
1
38
18
17
18
9
4
3
3
1
39
11
12
12
9
14
1...

output:

? 4 24
? 5 24
? 4 25
? 14 24
? 9 24
? 11 24
? 12 24
? 13 24
! 13 25
? 16 35
? 17 35
? 16 36
? 25 35
? 20 35
? 22 35
? 21 35
! 21 33
? 17 36
? 18 36
? 17 37
? 7 36
? 12 36
? 14 36
? 15 36
! 15 26
? 17 36
? 18 36
? 17 37
? 7 36
? 12 36
? 9 36
? 10 36
! 10 2
? 12 31
? 13 31
? 12 32
? 21 31
? 26 31
? 23...

result:

ok ok (1000 test cases)

Test #11:

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

input:

1000
40
14
15
15
10
9
10
9
8
1
40
20
14
15
15
10
11
11
10
1
40
13
12
12
10
15
13
12
1
40
14
15
15
10
13
11
12
1
40
16
15
17
6
5
4
5
1
40
3
2
4
9
4
1
2
1
41
14
15
13
10
15
17
16
15
1
40
19
19
19
9
5
7
7
1
40
20
18
17
19
8
5
6
5
6
1
40
12
11
11
10
11
10
9
10
1
40
8
9
9
10
9
7
6
1
41
5
6
4
10
6
4
3
1
4...

output:

? 13 33
? 14 33
? 13 34
? 3 33
? 8 33
? 5 33
? 6 33
? 7 33
! 7 26
? 19 39
? 16 36
? 17 36
? 16 37
? 6 36
? 11 36
? 13 36
? 12 36
! 12 27
? 2 22
? 3 22
? 2 23
? 12 22
? 7 22
? 4 22
? 3 22
! 3 33
? 4 24
? 5 24
? 4 25
? 34 24
? 39 24
? 1 24
? 40 24
! 1 14
? 11 31
? 12 31
? 11 32
? 21 31
? 26 31
? 23 31...

result:

ok ok (1000 test cases)

Test #12:

score: 0
Accepted
time: 8ms
memory: 3584kb

input:

1000
42
15
14
14
11
16
13
14
1
41
17
18
16
8
11
8
7
1
41
15
16
16
10
10
12
12
11
1
41
4
5
5
10
7
5
4
3
1
41
13
14
14
10
14
12
11
1
41
16
17
17
6
5
7
6
5
1
41
13
14
12
10
10
10
9
1
41
5
4
4
10
6
3
4
1
41
19
19
20
10
15
16
14
1
41
15
16
14
4
5
7
6
5
1
41
20
2
1
3
10
5
2
1
1
42
20
19
20
11
15
13
13
1
4...

output:

? 15 36
? 16 36
? 15 37
? 25 36
? 20 36
? 17 36
? 18 36
! 17 6
? 7 27
? 8 27
? 7 28
? 37 27
? 1 27
? 39 27
? 38 27
! 38 33
? 4 25
? 5 25
? 4 26
? 35 25
? 40 25
? 37 25
? 38 25
? 39 25
! 40 16
? 17 38
? 18 38
? 17 39
? 7 38
? 12 38
? 14 38
? 15 38
? 16 38
! 16 36
? 12 33
? 13 33
? 12 34
? 2 33
? 7 33...

result:

ok ok (1000 test cases)

Test #13:

score: 0
Accepted
time: 5ms
memory: 3712kb

input:

1000
43
4
5
5
11
10
7
6
5
1
42
18
17
19
11
13
11
10
11
1
43
21
15
16
16
10
13
12
12
11
1
43
15
16
16
11
9
10
9
8
1
43
15
16
14
10
9
8
7
1
43
16
15
15
11
13
14
13
12
1
43
19
20
18
8
5
5
6
6
1
43
21
21
20
21
19
9
5
6
5
1
42
13
14
14
2
5
3
2
1
1
42
20
19
20
10
6
8
8
1
42
15
14
14
11
10
8
9
1
43
17
18
1...

output:

? 3 24
? 4 24
? 3 25
? 35 24
? 40 24
? 43 24
? 1 24
? 2 24
! 3 21
? 8 29
? 9 29
? 8 30
? 18 29
? 13 29
? 15 29
? 16 29
? 17 29
! 16 20
? 14 35
? 9 31
? 10 31
? 9 32
? 41 31
? 3 31
? 6 31
? 4 31
? 5 31
! 5 21
? 21 42
? 22 42
? 21 43
? 10 42
? 15 42
? 12 42
? 13 42
? 14 42
! 14 35
? 13 34
? 14 34
? 13...

result:

ok ok (1000 test cases)

Test #14:

score: 0
Accepted
time: 5ms
memory: 3584kb

input:

1000
44
14
15
13
5
8
5
4
1
44
17
16
16
10
12
9
8
9
1
43
12
11
11
2
6
4
3
1
43
13
12
14
6
8
5
4
5
1
44
17
18
16
11
11
13
13
12
1
44
16
17
15
11
16
19
18
17
1
44
22
13
12
14
11
10
11
10
9
1
44
20
19
19
11
15
14
14
13
1
43
19
20
20
8
5
7
6
1
43
10
9
9
9
5
6
4
5
1
44
21
20
20
11
16
14
15
15
1
44
20
21
1...

output:

? 16 38
? 17 38
? 16 39
? 5 38
? 10 38
? 7 38
? 6 38
! 6 41
? 20 42
? 21 42
? 20 43
? 31 42
? 25 42
? 28 42
? 29 42
? 30 42
! 29 5
? 14 35
? 15 35
? 14 36
? 24 35
? 29 35
? 26 35
? 25 35
! 24 36
? 9 31
? 10 31
? 9 32
? 20 31
? 14 31
? 17 31
? 18 31
? 19 31
! 18 28
? 8 30
? 9 30
? 8 31
? 41 30
? 2 30...

result:

ok ok (1000 test cases)

Test #15:

score: 0
Accepted
time: 8ms
memory: 3712kb

input:

1000
45
19
20
18
11
17
18
17
1
45
17
16
16
11
14
15
14
13
1
45
10
9
11
11
7
8
7
6
1
45
21
20
20
10
6
9
9
10
1
45
18
19
19
11
16
15
17
16
1
45
7
6
6
11
6
5
4
5
1
45
19
18
20
8
6
7
7
6
1
45
21
20
20
10
6
9
11
1
44
19
18
20
8
3
3
4
1
45
22
14
13
13
3
6
4
2
3
1
44
20
19
21
9
4
1
2
1
45
16
15
17
12
18
16...

output:

? 7 29
? 8 29
? 7 30
? 40 29
? 1 29
? 4 29
? 5 29
! 5 45
? 8 30
? 9 30
? 8 31
? 19 30
? 13 30
? 10 30
? 11 30
? 12 30
! 12 42
? 1 23
? 2 23
? 1 24
? 12 23
? 6 23
? 3 23
? 4 23
? 5 23
! 5 18
? 20 43
? 21 43
? 20 44
? 31 43
? 37 43
? 34 43
? 32 43
? 33 43
! 32 6
? 5 28
? 6 28
? 5 29
? 39 28
? 44 28
? ...

result:

ok ok (1000 test cases)

Test #16:

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

input:

1000
46
14
13
13
9
9
6
7
1
46
5
4
4
12
8
5
4
1
46
20
19
19
12
15
15
16
1
46
19
20
18
11
15
16
14
1
46
9
10
10
11
11
8
7
1
46
19
18
18
8
6
9
7
8
1
46
18
19
19
11
12
14
14
13
1
46
22
21
21
12
17
15
16
15
1
46
22
21
22
11
6
8
7
7
1
46
3
4
2
11
7
4
3
2
1
45
18
17
19
7
6
5
6
1
46
6
7
5
11
10
7
6
5
1
46
1...

output:

? 3 26
? 4 26
? 3 27
? 14 26
? 8 26
? 11 26
? 12 26
! 11 31
? 3 26
? 4 26
? 3 27
? 14 26
? 8 26
? 5 26
? 4 26
! 4 29
? 2 25
? 3 25
? 2 26
? 13 25
? 7 25
? 10 25
? 8 25
! 7 39
? 16 39
? 17 39
? 16 40
? 4 39
? 10 39
? 13 39
? 11 39
! 11 6
? 3 26
? 4 26
? 3 27
? 37 26
? 43 26
? 46 26
? 1 26
! 1 20
? 2 ...

result:

ok ok (1000 test cases)

Test #17:

score: -100
Time Limit Exceeded

input:

1000
1000000000
499999999
499999999
499999998

output:

? 329695991 829695991
? 329695992 829695991
? 329695991 829695992
? -1067787657 829695991

result:
English 繁體中文 简体中文

伺服器時間: 2025-02-08 15:07:51 | 開源專案