QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#542793#8939. Permutationucup-team1231#RE 899ms57764kbPython33.8kb2024-09-01 05:45:172024-09-01 05:45:18

Judging History

This is the latest submission verdict.

  • [2024-09-01 05:45:18]
  • Judged
  • Verdict: RE
  • Time: 899ms
  • Memory: 57764kb
Show
  • [2024-09-01 05:45:17]
  • Submitted

answer

import sys
T = int(input())
def calc(u):
    if u<=1: return 0
    if u==2: return 1
    if u==3: return 2
    return 3+calc((u+3)//4)
import math
cnt = 0
arr = []
tl = 0
def qry(a,b):
    if a==b:
        return -1
    # u = list(range(a,b+1))
    # global cnt
    # global tl
    # tl += b-a+1
    # cnt += 1
    # u.sort(key=lambda s:-arr[s])
    # return u[1]
    print('?',a,b)
    sys.stdout.flush()
    return int(input())
def sol():
    import random
    # n = random.randint(1,100)
    n = int(input())
    global cnt, arr, tl
    arr = list(range(1,n+1))
    random.shuffle(arr)
    arr = [0] + arr
    cnt = 0
    tl = 0
    up = math.ceil(math.log2(n)*1.5)
    L, R = 1, n
    while R-L+1 >= 4:
        u = R-L+1
        ls = [u*i//4-u*(i-1)//4 for i in [1,2,3,4]]
        ls.sort()
        x = qry(L, R)
        if R-L+1 in [4,5]:
            if x == L:
                L += 1
                continue
            elif x == R:
                R -= 1
                continue
        # [fid[t],fid[t+1])
        c0 = 10**9
        fid0 = None
        def upd(fid):
            nonlocal c0, fid0
            inseg = lambda t,u: fid[t]<=u<fid[t+1]
            if inseg(0,x) or inseg(1,x):
                co = fid[2]+fid[3]-fid[0]*2
            else:
                co = fid[4]*2-fid[1]-fid[2]
            if co>=c0: return
            c0 = co
            fid0 = fid
        upd([L,L+ls[0],L+ls[0]+ls[1],L+ls[0]+ls[1]+ls[2],L+sum(ls)])
        upd([L,L+ls[0],L+ls[0]+ls[1],L+ls[0]+ls[1]+ls[-1],L+sum(ls)])
        ls = ls[::-1]
        upd([L,L+ls[0],L+ls[0]+ls[1],L+ls[0]+ls[1]+ls[2],L+sum(ls)])
        upd([L,L+ls[1],L+ls[0]+ls[1],L+ls[0]+ls[1]+ls[2],L+sum(ls)])
        fid = fid0
        inseg = lambda t,u: fid[t]<=u<fid[t+1]
        if inseg(0,x) or inseg(1,x):
            # x = 0
            # [0,2]
            if qry(fid[0],fid[2]-1) == x:
                if inseg(0,x):
                    if qry(fid[0],fid[1]-1) == x:
                        L, R = fid[0], fid[1]-1
                    else:
                        L, R = fid[1], fid[2]-1
                else:
                    if qry(fid[1],fid[2]-1) == x:
                        L, R = fid[1], fid[2]-1
                    else:
                        L, R = fid[0], fid[1]-1
            else:
                if qry(x,fid[3]-1) == x:
                    L, R = fid[2], fid[3]-1
                else:
                    L, R = fid[3], fid[4]-1
        else:
            if qry(fid[2],fid[4]-1) == x:
                if inseg(3,x):
                    if qry(fid[3],fid[4]-1) == x:
                        L, R = fid[3], fid[4]-1
                    else:
                        L, R = fid[2], fid[3]-1
                else:
                    if qry(fid[2],fid[3]-1) == x:
                        L, R = fid[2], fid[3]-1
                    else:
                        L, R = fid[3], fid[4]-1
            else:
                if qry(fid[1],x) == x:
                    L, R = fid[1], fid[2]-1
                else:
                    L, R = fid[0], fid[1]-1

    ans = -1
    # print(R-L+1)
    if R-L+1 == 3:
        x = qry(L,L+2)
        if x == L:
            L = x+1
        elif x == R:
            R = x-1
        else:
            assert x == L+1
            u = qry(L,x)
            if u == x:
                ans = L
            else:
                ans = R
    if ans == -1:
        if R-L+1 == 2:
            ans = qry(L,R)^L^R
        else:
            assert R-L+1 == 1
            ans = L
    print('!',ans)#,'@@',tl,'@@',n,'CC',cnt,'w',up)
#    print(arr[ans])
    # assert cnt <= up
    # assert ans!=-1 and arr[ans] == n
    # assert tl <= n*3##+2 #+2
    sys.stdout.flush()
for _ in range(T):
    sol()
Source code, Language: Python3

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 11200kb

input:

3
5
3
3
5
6
6
5
3
1
4
3
3

output:

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

result:

ok Correct (3 test cases)

Test #2:

score: 0
Accepted
time: 344ms
memory: 11020kb

input:

10000
10
2
2
1
3
10
10
7
10
5
4
10
5
5
5
5
6
10
4
4
4
4
10
10
9
6
3
2
10
3
3
4
2
10
1
4
5
9
9
10
1
3
1
5
6
10
2
4
4
9
8
10
3
3
3
3
10
4
1
7
8
9
10
8
7
7
1
2
10
4
1
5
9
8
10
7
8
7
4
6
10
5
5
7
8
10
10
8
8
7
9
10
2
1
2
7
5
10
6
6
5
10
8
10
1
3
1
5
6
10
7
9
5
1
2
10
7
8
4
1
2
10
3
4
4
10
8
10
4
1
4
7
6...

output:

? 1 10
? 1 4
? 1 2
? 3 4
! 4
? 1 10
? 7 10
? 4 10
? 4 6
? 4 5
! 6
? 1 10
? 5 10
? 5 7
? 5 7
? 6 7
! 7
? 1 10
? 1 4
? 3 4
? 3 4
! 3
? 1 10
? 7 10
? 4 10
? 1 3
? 1 2
! 1
? 1 10
? 1 4
? 3 4
? 1 2
! 1
? 1 10
? 1 4
? 1 7
? 8 10
? 8 9
! 8
? 1 10
? 1 4
? 1 7
? 5 7
? 6 7
! 7
? 1 10
? 1 4
? 2 7
? 8 10
? 8 9
...

result:

ok Correct (10000 test cases)

Test #3:

score: 0
Accepted
time: 396ms
memory: 11044kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #4:

score: 0
Accepted
time: 534ms
memory: 11104kb

input:

10000
47
23
23
19
11
9
11
5
5
14
8
8
8
8
7
9
25
6
12
6
13
13
7
4
4
4
4
9
2
2
2
2
27
27
27
27
27
26
24
23
21
7
7
6
5
3
3
43
41
37
21
7
8
5
3
1
22
6
4
14
20
20
19
21
34
29
25
29
17
17
18
16
42
20
20
20
20
20
19
17
47
21
21
21
21
21
22
19
19
41
25
25
30
33
34
33
36
38
19
17
17
16
12
12
21
14
14
14
14
1...

output:

? 1 47
? 1 23
? 12 23
? 1 11
? 7 11
? 4 11
? 4 6
? 4 5
! 4
? 1 14
? 7 14
? 7 10
? 7 10
? 7 8
? 8 9
! 10
? 1 25
? 1 12
? 6 18
? 13 18
? 13 14
! 14
? 1 7
? 4 7
? 4 5
? 4 5
! 5
? 1 9
? 1 4
? 1 2
? 1 2
! 1
? 1 27
? 15 27
? 22 27
? 22 27
? 26 27
? 24 27
? 22 23
! 22
? 1 21
? 1 10
? 6 10
? 1 5
? 1 4
? 3 4...

result:

ok Correct (10000 test cases)

Test #5:

score: 0
Accepted
time: 666ms
memory: 11108kb

input:

10000
100
47
5
47
61
53
68
71
71
71
71
9
2
2
1
4
53
46
35
15
6
6
6
6
4
33
3
16
16
31
31
30
32
82
60
56
60
29
29
28
23
22
24
26
88
39
8
39
59
59
59
59
61
59
71
24
29
29
59
54
59
65
66
64
63
92
52
52
56
88
88
88
88
89
91
91
24
11
11
9
5
6
5
3
66
51
51
66
45
43
45
39
40
42
92
43
43
38
20
20
21
17
17
48...

output:

? 1 100
? 1 50
? 47 75
? 51 75
? 51 62
? 61 68
? 69 75
? 69 71
? 70 71
? 70 71
! 70
? 1 9
? 1 4
? 1 2
? 3 4
! 3
? 1 53
? 28 53
? 15 46
? 1 14
? 1 6
? 4 6
? 4 6
? 4 5
! 5
? 1 33
? 1 16
? 3 24
? 25 33
? 30 33
? 30 31
? 32 33
! 33
? 1 82
? 43 82
? 22 60
? 22 42
? 22 31
? 27 31
? 22 26
? 22 23
? 23 24
?...

result:

ok Correct (10000 test cases)

Test #6:

score: 0
Accepted
time: 684ms
memory: 11044kb

input:

10000
50
10
10
10
10
7
10
6
5
50
11
11
9
18
16
21
23
22
50
44
40
44
20
20
21
26
25
23
50
24
14
29
45
45
45
45
46
50
50
50
50
50
50
49
47
45
50
36
39
23
12
12
11
8
10
50
29
36
20
13
12
6
3
3
50
30
42
22
1
1
1
1
2
50
25
25
25
25
25
27
30
29
50
18
20
20
49
47
47
39
39
50
9
9
9
9
9
7
11
10
50
26
43
26
1...

output:

? 1 50
? 1 24
? 1 12
? 1 12
? 7 12
? 4 10
? 4 6
? 4 5
! 4
? 1 50
? 1 24
? 1 12
? 13 24
? 13 18
? 18 21
? 22 24
? 22 23
! 24
? 1 50
? 27 50
? 14 44
? 14 26
? 20 26
? 20 22
? 23 26
? 23 25
? 23 24
! 24
? 1 50
? 1 24
? 24 37
? 38 50
? 45 50
? 45 47
? 45 47
? 46 47
! 47
? 1 50
? 27 50
? 39 50
? 39 50
? ...

result:

ok Correct (10000 test cases)

Test #7:

score: 0
Accepted
time: 899ms
memory: 11188kb

input:

10000
100
76
78
35
5
5
3
9
9
9
9
100
29
29
50
20
20
20
20
21
22
24
100
64
64
69
88
100
88
86
87
84
83
100
51
51
57
98
92
92
79
79
80
81
100
44
44
50
13
24
13
12
11
11
7
100
64
92
64
41
44
41
33
34
35
37
100
93
56
93
40
40
44
49
50
47
45
100
37
2
37
57
54
60
74
75
73
70
100
76
76
76
76
76
80
86
87
86...

output:

? 1 100
? 51 100
? 26 76
? 1 25
? 1 12
? 1 6
? 7 12
? 9 12
? 9 10
? 9 10
! 10
? 1 100
? 1 50
? 26 50
? 1 25
? 14 25
? 20 25
? 20 25
? 20 21
? 20 23
? 24 25
! 25
? 1 100
? 51 100
? 51 75
? 76 100
? 88 100
? 82 88
? 82 87
? 86 87
? 84 86
? 82 83
! 82
? 1 100
? 51 100
? 51 75
? 76 100
? 89 100
? 83 98
...

result:

ok Correct (10000 test cases)

Test #8:

score: 0
Accepted
time: 370ms
memory: 11096kb

input:

1000
1000
475
426
728
896
974
896
867
867
869
858
860
851
847
847
1000
278
17
278
598
534
598
679
665
679
652
655
647
641
642
643
1000
75
128
75
607
604
644
713
695
732
749
745
749
742
741
739
1000
239
239
45
432
432
429
442
442
451
458
459
458
462
461
463
1000
978
978
978
978
978
997
914
914
920
93...

output:

? 1 1000
? 1 500
? 475 750
? 751 1000
? 877 1000
? 814 896
? 814 876
? 846 876
? 862 876
? 846 861
? 854 861
? 850 858
? 846 849
? 846 847
! 846
? 1 1000
? 1 500
? 278 750
? 501 750
? 501 624
? 598 687
? 625 687
? 657 687
? 641 679
? 641 656
? 649 656
? 645 652
? 641 644
? 642 644
? 643 644
! 644
? ...

result:

ok Correct (1000 test cases)

Test #9:

score: 0
Accepted
time: 368ms
memory: 11232kb

input:

1017
272
246
186
246
111
110
110
73
73
73
73
75
75
114
105
91
91
2
2
2
2
2
3
910
173
173
173
173
127
127
14
28
29
56
51
56
48
47
48
726
229
229
201
118
149
63
28
28
28
28
28
29
26
861
315
104
315
491
528
551
632
641
614
593
593
594
597
596
1984
133
133
406
571
571
512
724
704
704
650
650
650
650
651...

output:

? 1 272
? 137 272
? 69 246
? 69 136
? 103 136
? 86 111
? 69 85
? 69 76
? 73 76
? 73 76
? 74 76
? 74 75
! 74
? 1 114
? 59 114
? 30 105
? 1 29
? 1 14
? 1 7
? 1 7
? 1 3
? 2 3
! 1
? 1 910
? 1 454
? 1 227
? 1 227
? 115 227
? 58 173
? 1 57
? 1 28
? 14 42
? 43 57
? 51 57
? 47 56
? 47 50
? 47 48
? 48 49
! 4...

result:

ok Correct (1017 test cases)

Test #10:

score: 0
Accepted
time: 341ms
memory: 18828kb

input:

10
100000
3893
3893
3505
30673
33920
30673
43582
43582
43582
43582
43582
43470
43242
43242
43197
43289
43289
43298
43268
43268
43267
43273
43272
43273
100000
32066
19090
54928
88585
88585
88585
88585
89959
88585
91599
91474
91599
91257
91257
91225
91398
91383
91398
91339
91337
91339
91348
91347
9134...

output:

? 1 100000
? 1 50000
? 1 25000
? 25001 50000
? 25001 37500
? 30673 43750
? 37501 43750
? 40627 43750
? 42189 43750
? 42189 43750
? 42971 43750
? 43361 43750
? 42971 43360
? 43167 43360
? 43167 43263
? 43264 43360
? 43264 43311
? 43288 43311
? 43264 43287
? 43264 43275
? 43264 43269
? 43270 43275
? 4...

result:

ok Correct (10 test cases)

Test #11:

score: 0
Accepted
time: 359ms
memory: 23816kb

input:

21
84335
47947
60969
22445
9296
1509
11772
20931
19830
20931
17510
17510
17606
17352
17352
17352
17352
17346
17352
17338
17337
17328
17320
17320
17321
17323
159962
128177
145530
128177
54814
54814
59035
49869
48003
49869
43214
43214
43214
43214
43231
43550
43675
43675
43675
43675
43670
43689
43695
4...

output:

? 1 84335
? 42169 84335
? 21085 47947
? 1 21084
? 1 10542
? 9296 15813
? 15814 21084
? 18450 21084
? 17132 20931
? 17132 18449
? 17132 17789
? 17461 17789
? 17132 17460
? 17297 17460
? 17297 17378
? 17297 17378
? 17339 17378
? 17318 17352
? 17318 17338
? 17329 17338
? 17324 17338
? 17318 17323
? 173...

result:

ok Correct (21 test cases)

Test #12:

score: 0
Accepted
time: 490ms
memory: 57764kb

input:

1
1000000
641602
641602
561698
783270
783270
783270
783270
783270
783270
783270
786055
786055
794273
794682
794682
796734
796734
796734
796734
796686
796788
796850
796850
796851
796864
796864
796866
796861
796863

output:

? 1 1000000
? 500001 1000000
? 500001 750000
? 750001 1000000
? 750001 875000
? 750001 812500
? 750001 812500
? 781251 812500
? 781251 796875
? 781251 796875
? 781251 789062
? 783270 792968
? 792969 796875
? 792969 794921
? 794273 795898
? 795899 796875
? 796388 796875
? 796632 796875
? 796632 79687...

result:

ok Correct (1 test case)

Test #13:

score: 0
Accepted
time: 386ms
memory: 39860kb

input:

16
232936
229707
229707
229707
229707
229707
229707
229707
231039
229707
223556
223533
224031
225261
225261
225261
225261
225290
225290
225375
225395
225407
225417
225419
225417
225425
225425
8676
6498
6498
6498
6498
5867
4978
4731
4731
4731
4731
4731
4717
4684
4684
4681
4692
4692
4691
4693
221085
1...

output:

? 1 232936
? 116469 232936
? 174703 232936
? 174703 232936
? 203821 232936
? 218379 232936
? 218379 232936
? 225659 232936
? 222019 229707
? 222019 225658
? 222019 223838
? 223556 224748
? 224749 225658
? 225205 225658
? 225205 225431
? 225205 225431
? 225205 225317
? 225261 225374
? 225375 225431
?...

result:

ok Correct (16 test cases)

Test #14:

score: -100
Dangerous Syscalls

input:

1994
667
666
667
665
167
166
166
42
41
41
11
10
10
3
2
374
373
374
372
94
93
93
24
23
23
6
5
5
2
488
486
488
485
122
121
121
31
30
30
8
7
7
2
922
921
922
920
231
230
230
58
57
57
15
14
14
4
3
2
639
637
639
636
160
159
159
40
39
39
10
9
9
3
2
353
350
353
349
89
88
88
23
22
22
6
5
5
2
71
66
71
65
18
1...

output:

? 1 667
? 335 667
? 168 666
? 1 167
? 85 167
? 43 167
? 1 42
? 23 42
? 12 42
? 1 11
? 7 11
? 4 11
? 1 3
? 1 2
! 1
? 1 374
? 189 374
? 95 373
? 1 94
? 49 94
? 25 94
? 1 24
? 13 24
? 7 24
? 1 6
? 5 6
? 3 6
? 1 2
! 1
? 1 488
? 245 488
? 123 486
? 1 122
? 63 122
? 32 122
? 1 31
? 17 31
? 9 31
? 1 8
? 5 ...

result:
English 繁體中文 简体中文

Server Time: 2025-02-11 09:51:35 | OpenSource Project