QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#867090#9734. Identify ChordZawosAC ✓51ms3712kbC++205.3kb2025-01-23 06:18:292025-01-23 06:18:29

Judging History

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

  • [2025-01-23 06:18:29]
  • 评测
  • 测评结果：AC
  • 用时：51ms
  • 内存：3712kb
查看
  • [2025-01-23 06:18:29]
  • 提交

answer

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define FOR(i,a,b) for (int i = (a); i < (b); i++)
using namespace std;
using namespace __gnu_pbds;
using ll=long long;
using ld=long double;
using vi=vector<ll>;
template<class T> using oset =tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update> ;
//上
ll n;
ll ask(ll x,ll y){
    ll r;
    cout <<"? "<<x+1<<" "<<y+1<<endl;
    cin >> r;
    return r;
}
void f(ll x,ll y){
    cout <<"! "<<x+1<<" "<<y+1<<endl;
    return;
}
ll nxt(ll a,ll d){
    a = (a%n+n)%n;
    d = (d%n+n)%n;
    a += d;
    a %= n;
    return a;
}
void brute(){
    for(ll i = 0; i < n;i++){
        for(ll j = i+1; j < n; j++){
            if(nxt(j,1) != i && nxt(i,1) != j){
                ll r = ask(i,j);
                if(r == 1){
                    f(i,j);
                    return;
                }
            }
        }
    }
    return;
}
void bin(ll a,ll pos,ll s1,ll s2,ll p){
                        ll ans = 0;
                        ll dis = a;
                        ll l = 0;
                        ll r = n;
                        while(l <= r){
                            ll mid =(l+r)/2;
                            
                            ll o = ask(nxt(pos,s1*mid),nxt(pos,p+s2*mid));
                            if(o +2*mid== a){
                                dis = o;
                                ans = mid;
                                l = mid+1;
                            }else r = mid -1;
                        }
                        if(ans == 0){
                            ll x = ask(nxt(pos,s1*ans),nxt(pos,p+s2*(ans+(dis-1))));
                            ll y = ask(nxt(pos,s1*(ans+(dis-1))),nxt(pos,p+s2*ans));
                            ll c = ask(nxt(pos,s1*ans),nxt(pos,p-s2*(ans+(dis-1))));
                            ll d = ask(nxt(pos,-s1*(ans+(dis-1))),nxt(pos,p+s2*ans));
                            if(x == 1){
                                f(nxt(pos,s1*ans),nxt(pos,p+s2*(ans+(dis-1))));
                            }else if(y == 1){
                                f(nxt(pos,s1*(ans+(dis-1))),nxt(pos,p+s2*ans));
                            }else if(c == 1){
                                f(nxt(pos,s1*ans),nxt(pos,p-s2*(ans+(dis-1))));
                            }else f(nxt(pos,-s1*(ans+(dis-1))),nxt(pos,p+s2*ans));
                            return;
                        }
                        ll x = ask(nxt(pos,s1*ans),nxt(pos,p+s2*(ans+(dis-1))));
                        if(x == 1){
                            f(nxt(pos,s1*ans),nxt(pos,p+s2*(ans+(dis-1))));
                            return;
                        }else{
                            f(nxt(pos,s1*(ans+(dis-1))),nxt(pos,p+s2*ans));
                            return;                            
                        }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll t;
    cin >> t;
    ll correct;
    
    while(t--){
        cin >> n;
        if(n < 8){
            brute();
        }else{
            if(n%2== 1){
                ll a = ask(0,n/2);
                ll b = ask(0,n/2+1);
                ll pos = 0;
                if(a == n/2 && b == n/2){
                    pos = (n/2)/2;
                    a = ask(pos,nxt(pos,n/2));
                    b = ask(pos,nxt(pos,n/2+1));
                }
                assert(a != n/2 || b !=n/2);
                if(a == 1){
                    f(pos,nxt(pos,n/2));
                    cin >> correct;
                    continue;
                }
                if(b == 1){
                    f(pos,nxt(pos,n/2+1));
                    cin >> correct;
                    continue;
                }
                ll c,d;
                if(a < b){
                    c = ask(nxt(pos,1),nxt(pos,n/2-1));
                    if(a == c+2){
                        bin(a,pos,1,-1,n/2);
                    }else{
                        bin(a,pos,-1,-1,n/2);
                    }
                }else{
                    d = ask(nxt(pos,-1),nxt(pos,n/2+1+1));
                    if(b == d+2){
                        bin(b,pos,-1,1,n/2+1);
                    }else{
                        bin(b,pos,1,1,n/2+1);
                    }
                }
            }else{
                ll a = ask(0,n/2);
                ll pos = 0;
                if(a == n/2){
                    pos = (n/2)/2;
                    a = ask(pos,nxt(pos,n/2));
                }
                assert(a != n/2);
                if(a == 1){
                    f(pos,nxt(pos,n/2));
                    cin >> correct;
                    continue;
                }
                ll c = ask(nxt(pos,1),nxt(pos,n/2-1));
                ll d = ask(nxt(pos,-1),nxt(pos,n/2+1));
                ll e = ask(pos,nxt(pos,n/2+1));
                if(a == c+2){
                        bin(a,pos,1,-1,n/2);
                }else if(a == d+2){
                        bin(a,pos,-1,1,n/2);
                }else if(a == e+1){
                        bin(a,pos,1,1,n/2);
                }else{
                        bin(a,pos,-1,-1,n/2);
                }

            }
        }
        cin >> correct;
    }
}
Source code, Language: C++20

这程序好像有点Bug，我给组数据试试？

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2
6
2
2
2
1
1
4
1
1

output:

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

result:

ok ok (2 test cases)

Test #2:

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

input:

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

output:

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

result:

ok ok (1000 test cases)

Test #3:

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

input:

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

output:

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

result:

ok ok (1000 test cases)

Test #4:

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

input:

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

output:

? 1 13
? 1 14
? 2 12
? 14 1
? 21 8
? 24 11
? 1 13
? 25 12
? 1 6
? 19 13
? 1 20
? 8 13
! 1 6
? 1 13
? 1 14
? 2 12
? 14 1
? 21 8
? 24 11
? 1 13
? 25 12
? 25 9
! 25 9
? 1 13
? 1 14
? 2 12
? 14 1
? 21 8
? 24 11
? 23 10
? 22 9
? 23 6
! 23 6
? 1 13
? 1 14
? 2 12
? 13 1
? 6 8
? 3 11
? 4 10
? 3 11
! 3 11
? ...

result:

ok ok (1000 test cases)

Test #5:

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

input:

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

output:

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

result:

ok ok (1000 test cases)

Test #6:

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

input:

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

output:

? 1 17
? 2 16
? 32 18
? 1 18
? 17 1
? 8 10
? 4 14
? 6 12
? 5 13
? 5 9
! 5 9
? 1 16
? 2 15
? 30 17
? 1 17
? 16 1
? 24 23
? 28 19
? 26 21
? 27 20
? 28 26
! 28 26
? 1 17
? 9 25
? 10 24
? 8 26
? 9 26
? 25 9
? 16 32
? 12 28
? 10 26
? 9 25
? 9 26
? 10 25
? 9 24
? 8 25
! 9 26
? 1 16
? 1 17
? 2 15
? 16 1
? ...

result:

ok ok (1000 test cases)

Test #7:

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

input:

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

output:

? 1 18
? 9 26
? 10 25
? 8 27
? 9 27
? 26 9
? 1 34
? 6 29
? 4 31
? 5 30
? 5 31
! 5 31
? 1 17
? 1 18
? 2 16
? 17 1
? 8 10
? 4 14
? 2 16
? 3 15
? 3 12
! 6 15
? 1 17
? 1 18
? 33 19
? 18 1
? 27 25
? 31 21
? 29 23
? 30 22
? 31 24
! 31 24
? 1 18
? 2 17
? 34 19
? 1 19
? 18 1
? 27 10
? 32 15
? 30 13
? 31 14
...

result:

ok ok (1000 test cases)

Test #8:

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

input:

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

output:

? 1 19
? 10 28
? 11 27
? 9 29
? 10 29
? 28 10
? 18 20
? 23 15
? 20 18
? 19 19
? 18 20
! 18 20
? 1 19
? 2 18
? 36 20
? 1 20
? 19 1
? 29 11
? 34 16
? 36 18
? 1 19
? 1 17
? 35 19
? 1 21
? 3 19
! 35 19
? 1 19
? 2 18
? 36 20
? 1 20
? 19 1
? 9 11
? 4 16
? 6 14
? 5 15
? 4 10
! 4 10
? 1 19
? 2 18
? 36 20
? ...

result:

ok ok (1000 test cases)

Test #9:

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

input:

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

output:

? 1 19
? 1 20
? 2 18
? 20 1
? 30 11
? 35 16
? 33 14
? 32 13
? 33 8
! 27 14
? 1 19
? 2 18
? 36 20
? 1 20
? 19 1
? 29 27
? 34 22
? 32 24
? 31 25
? 30 26
? 30 28
! 28 26
? 1 20
? 2 19
? 38 21
? 1 21
? 20 1
? 10 11
? 5 16
? 2 19
? 3 18
? 4 17
? 3 14
! 7 18
? 1 19
? 1 20
? 37 21
? 19 1
? 9 28
? 4 23
? 2 ...

result:

ok ok (1000 test cases)

Test #10:

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

input:

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

output:

? 1 20
? 1 21
? 39 22
? 20 1
? 10 30
? 5 25
? 7 27
? 6 26
? 5 33
! 13 25
? 1 20
? 2 19
? 38 21
? 1 21
? 20 1
? 30 29
? 35 24
? 38 21
? 37 22
? 38 26
! 33 21
? 1 20
? 10 29
? 11 28
? 9 30
? 10 30
? 29 10
? 19 20
? 14 25
? 11 28
? 12 27
? 13 26
? 13 24
! 15 26
? 1 20
? 1 21
? 2 19
? 20 1
? 10 11
? 5 1...

result:

ok ok (1000 test cases)

Test #11:

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

input:

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

output:

? 1 21
? 2 20
? 40 22
? 1 22
? 21 1
? 10 30
? 5 25
? 7 27
? 6 26
? 6 27
! 7 26
? 1 21
? 2 20
? 40 22
? 1 22
? 21 1
? 10 30
? 5 25
? 7 27
? 8 28
? 7 32
! 12 27
? 1 21
? 2 20
? 40 22
? 1 22
? 21 1
? 10 30
? 5 25
? 2 22
? 3 23
? 4 24
? 3 33
! 3 33
? 1 21
? 2 20
? 40 22
? 1 22
? 21 1
? 32 12
? 37 17
? 4...

result:

ok ok (1000 test cases)

Test #12:

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

input:

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

output:

? 1 22
? 2 21
? 42 23
? 1 23
? 22 1
? 11 12
? 5 18
? 8 15
? 6 17
? 7 16
? 6 17
! 6 17
? 1 21
? 1 22
? 41 23
? 22 1
? 33 31
? 38 26
? 36 28
? 37 27
? 38 33
! 38 33
? 1 21
? 1 22
? 2 20
? 22 1
? 33 12
? 38 17
? 41 20
? 40 19
? 39 18
? 40 16
! 40 16
? 1 21
? 1 22
? 2 20
? 22 1
? 33 12
? 38 17
? 36 15
?...

result:

ok ok (1000 test cases)

Test #13:

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

input:

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

output:

? 1 22
? 1 23
? 2 21
? 22 1
? 11 12
? 5 18
? 2 21
? 3 20
? 2 20
! 3 21
? 1 22
? 2 21
? 42 23
? 1 23
? 22 1
? 11 12
? 5 18
? 2 21
? 3 20
? 4 19
? 3 7
! 16 20
? 1 22
? 1 23
? 2 21
? 22 1
? 11 12
? 5 18
? 2 21
? 3 20
? 2 18
! 5 21
? 1 22
? 1 23
? 2 21
? 23 1
? 34 12
? 40 18
? 37 15
? 36 14
? 35 13
? 36...

result:

ok ok (1000 test cases)

Test #14:

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

input:

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

output:

? 1 23
? 12 34
? 13 33
? 11 35
? 12 35
? 34 12
? 2 44
? 8 38
? 5 41
? 7 39
? 6 40
? 6 41
! 6 41
? 1 23
? 2 22
? 44 24
? 1 24
? 23 1
? 11 33
? 5 27
? 8 30
? 6 28
? 5 29
! 5 29
? 1 22
? 1 23
? 43 24
? 23 1
? 34 33
? 40 27
? 43 24
? 42 25
? 43 31
! 36 24
? 1 22
? 1 23
? 11 32
? 11 33
? 12 31
? 32 11
? ...

result:

ok ok (1000 test cases)

Test #15:

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

input:

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

output:

? 1 23
? 1 24
? 2 22
? 24 1
? 36 13
? 42 19
? 45 22
? 44 21
? 45 5
! 45 5
? 1 23
? 1 24
? 2 22
? 24 1
? 36 13
? 42 19
? 39 16
? 41 18
? 42 12
! 42 12
? 1 23
? 1 24
? 2 22
? 23 1
? 11 13
? 5 19
? 8 16
? 6 18
? 5 18
! 5 18
? 1 23
? 1 24
? 45 25
? 23 1
? 11 34
? 5 28
? 8 31
? 6 29
? 7 30
? 6 32
! 6 32
...

result:

ok ok (1000 test cases)

Test #16:

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

input:

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

output:

? 1 24
? 2 23
? 46 25
? 1 25
? 24 1
? 12 35
? 6 29
? 9 32
? 7 30
? 8 31
? 8 34
! 11 31
? 1 24
? 2 23
? 46 25
? 1 25
? 24 1
? 12 35
? 6 29
? 3 26
? 4 27
? 5 28
? 4 29
! 4 29
? 1 24
? 2 23
? 46 25
? 1 25
? 24 1
? 12 35
? 6 29
? 9 32
? 7 30
? 8 31
? 7 39
! 7 39
? 1 24
? 2 23
? 46 25
? 1 25
? 24 1
? 12 ...

result:

ok ok (1000 test cases)

Test #17:

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

input:

1000
1000000000
499999999
499999998
499999997
499999998
499999999
2
250000001
125000002
187500002
218750002
234375002
242187502
246093751
244140627
243164066
243652348
243896488
244018558
244079594
244110111
244094853
244087224
244091040
244092948
244093902
244094378
244094616
244094736
244094795
24...

output:

? 1 500000001
? 2 500000000
? 1000000000 500000002
? 1 500000002
? 500000001 1
? 750000002 750000000
? 875000002 625000000
? 812500002 687500000
? 843750002 656250000
? 859375002 640625000
? 867187502 632812500
? 871093752 628906250
? 873046877 626953125
? 872070315 627929687
? 871582034 628417968
?...

result:

ok ok (1000 test cases)

Test #18:

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

input:

1000
1000000000
499999969
499999967
499999971
499999970
499999969
2
250000002
374999971
312499971
281250002
296875002
304687502
308593721
306640597
305664066
306152348
306396488
306518527
306457524
306488042
306503269
306495672
306499486
306501394
306502317
306501841
306501634
306501754
306501783
30...

output:

? 1 500000001
? 2 500000000
? 1000000000 500000002
? 1 500000002
? 500000001 1
? 250000000 250000002
? 125000000 375000002
? 62500000 437500002
? 93750000 406250002
? 109375000 390625002
? 101562500 398437502
? 97656250 402343752
? 95703125 404296877
? 96679687 403320315
? 97167968 402832034
? 96923...

result:

ok ok (1000 test cases)

Test #19:

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

input:

1000
1000000000
474148191
474148191
474148191
474148190
474148191
25851809
224148193
99148193
36648193
5398193
10226809
2414309
1491943
461183
515381
27101
217041
94971
33935
3417
11843
4215
401
1509
555
77
163
45
17
15
1
9
5
3
1
1
1000000000
479245617
479245617
479245617
479245618
479245617
2075438...

output:

? 1 500000001
? 2 500000000
? 1000000000 500000002
? 1 500000002
? 500000001 1
? 250000000 750000000
? 125000000 625000000
? 187500000 687500000
? 218750000 718750000
? 234375000 734375000
? 242187500 742187500
? 238281250 738281250
? 236328125 736328125
? 237304687 737304687
? 236816406 736816406
?...

result:

ok ok (1000 test cases)

Test #20:

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

input:

1000
1000000000
230485382
230485382
230485382
230485383
230485382
269514618
19514618
105485384
42985384
11735384
3889618
3922884
16634
1936492
959930
471648
227508
105438
44402
13884
1376
6254
2440
532
424
72
186
72
128
98
84
76
72
72
143
1
1000000000
237329401
237329401
237329401
237329400
23732940...

output:

? 1 500000001
? 2 500000000
? 1000000000 500000002
? 1 500000002
? 500000001 1
? 750000002 250000002
? 875000002 375000002
? 937500002 437500002
? 906250002 406250002
? 890625002 390625002
? 882812502 382812502
? 886718752 386718752
? 884765627 384765627
? 883789065 383789065
? 884277346 384277346
?...

result:

ok ok (1000 test cases)

Test #21:

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

input:

1000
1000000000
288090905
288090907
288090903
288090904
288090905
2
204346805
204346805
225590907
204346805
209965907
204346805
206059657
204346805
205083095
204594815
204350675
204346805
204346805
204346805
204346805
204346805
204346861
204346805
204346805
204346805
204346805
204346805
204346805
20...

output:

? 1 500000001
? 2 500000000
? 1000000000 500000002
? 1 500000002
? 500000001 1
? 750000002 750000000
? 875000002 625000000
? 937500002 562500000
? 968750002 531250000
? 953125002 546875000
? 960937502 539062500
? 957031252 542968750
? 958984377 541015625
? 958007815 541992187
? 958496096 541503906
?...

result:

ok ok (1000 test cases)

Test #22:

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

input:

1000
999999999
499999998
499999999
499999996
499999998
1
250000000
125000000
62500001
93750000
78125000
70312500
66406250
64453126
63476564
62988282
62744143
62866212
62805178
62774660
62759403
62767032
62763218
62761311
62762265
62762743
62762980
62762863
62762922
62762893
62762908
62762901
6276290...

output:

? 1 500000000
? 1 500000001
? 2 499999999
? 500000000 1
? 250000000 250000001
? 125000000 375000001
? 187500000 312500001
? 218750000 281250001
? 203125000 296875001
? 210937500 289062501
? 214843750 285156251
? 216796875 283203126
? 217773437 282226564
? 218261718 281738283
? 218505859 281494142
? ...

result:

ok ok (1000 test cases)

Test #23:

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

input:

1000
999999999
499999957
499999956
499999954
499999956
1
249999958
124999958
62500001
93750001
109375001
117187501
121093751
123046877
124023396
123535159
123779256
123657186
123596195
123626713
123641971
123649558
123645787
123647682
123648606
123648130
123647892
123647772
123647712
123647682
12364...

output:

? 1 500000000
? 1 500000001
? 999999999 500000002
? 500000001 1
? 750000001 750000000
? 875000001 625000000
? 812500001 687500000
? 781250001 718750000
? 796875001 703125000
? 804687501 695312500
? 808593751 691406250
? 810546876 689453125
? 811523439 688476562
? 812011720 687988281
? 811767580 6882...

result:

ok ok (1000 test cases)

Test #24:

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

input:

1000
999999999
324545945
324545944
324545944
324545945
175454056
74545946
50454056
12045946
19204056
3579056
4233446
327196
1625930
649368
161086
83056
39016
22022
8498
6764
868
2950
1042
88
390
152
32
30
2
16
8
4
2
3
1
999999999
446446636
446446635
446446635
446446636
53553365
196446637
71446637
89...

output:

? 1 500000000
? 1 500000001
? 999999999 500000002
? 500000000 1
? 250000000 750000000
? 125000000 625000000
? 187500000 687500000
? 156250000 656250000
? 171875000 671875000
? 164062500 664062500
? 160156250 660156250
? 162109375 662109375
? 163085937 663085937
? 162597656 662597656
? 162353515 6623...

result:

ok ok (1000 test cases)

Test #25:

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

input:

1000
999999999
487015083
487015084
487015083
487015084
12984917
237015085
112015085
49515085
18265085
2640085
5172417
1266167
686961
289603
198681
45461
76611
15577
14943
319
7313
3497
1589
635
159
81
67
67
67
67
67
67
133
1
999999999
307120211
307120210
307120210
307120211
192879790
57120212
678797...

output:

? 1 500000000
? 1 500000001
? 2 499999999
? 500000001 1
? 750000001 250000001
? 875000001 375000001
? 812500001 312500001
? 781250001 281250001
? 765625001 265625001
? 757812501 257812501
? 753906251 253906251
? 755859376 255859376
? 756835939 256835939
? 756347658 256347658
? 756591799 256591799
? ...

result:

ok ok (1000 test cases)

Test #26:

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

input:

1000
999999999
265285129
265285128
265285128
265285129
249264884
249264884
249264884
249264884
249264884
249660130
249264884
249264884
249264884
249264884
249264884
249415990
249293920
249264884
249264884
249278662
249271034
249267220
249265312
249264884
249264884
249265074
249264956
249264896
24926...

output:

? 1 500000000
? 1 500000001
? 999999999 500000002
? 500000000 1
? 250000000 750000000
? 125000000 625000000
? 62500000 562500000
? 31250000 531250000
? 15625000 515625000
? 7812500 507812500
? 11718750 511718750
? 9765625 509765625
? 8789062 508789062
? 8300781 508300781
? 8056640 508056640
? 793457...

result:

ok ok (1000 test cases)

Test #27:

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

input:

1000
536870912
261621269
261621269
261621269
261621270
261621269
108355805
127403543
108355805
108355805
110626327
108355805
108355805
108529175
108355805
108355805
108355805
108398103
108355805
108365335
108355805
108357143
108355805
108355805
108356119
108355805
108355863
108355805
108355805
10835...

output:

? 1 268435457
? 2 268435456
? 536870912 268435458
? 1 268435458
? 268435457 1
? 402653186 134217730
? 469762050 201326594
? 436207618 167772162
? 452984834 184549378
? 461373442 192937986
? 457179138 188743682
? 459276290 190840834
? 460324866 191889410
? 459800578 191365122
? 460062722 191627266
? ...

result:

ok ok (1000 test cases)

Test #28:

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

input:

1000
536870911
244408485
244408484
244408482
244408484
1
115648538
177299622
143745190
126967974
118579366
115648538
116482214
115648538
115957926
115695782
115648538
115648538
115663014
115648538
115654822
115650726
115648678
115648538
115648538
115648538
115648550
115648538
115648538
115648538
115...

output:

? 1 268435456
? 1 268435457
? 536870911 268435458
? 268435457 1
? 402653185 402653184
? 469762049 335544320
? 503316481 301989888
? 486539265 318767104
? 478150657 327155712
? 473956353 331350016
? 471859201 333447168
? 472907777 332398592
? 472383489 332922880
? 472645633 332660736
? 472514561 3327...

result:

ok ok (1000 test cases)

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

Server Time: 2025-02-01 13:52:34 | OpenSource Project