QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#666631#8939. Permutationxh_teamWA 115ms3860kbC++141.8kb2024-10-22 19:26:282024-10-22 19:26:45

Judging History

This is the latest submission verdict.

  • [2024-10-22 19:26:45]
  • Judged
  • Verdict: WA
  • Time: 115ms
  • Memory: 3860kb
Show
  • [2024-10-22 19:26:28]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
const int N = 2014;

mt19937 rnd(time(0));

int a[] = {-1, 4, 7, 2, 6, 5, 1, 9};

int ask(int l, int r) {
    cout << '?' << ' ' << l << ' ' << r << endl;
    int x;
    cin >> x;
    return x;


    // int fi = -1, se = -1;
    // for (int i = l; i <= r; i++) {
    //     fi = max(fi, a[i]);
    // }
    // int x = -1;
    // for (int i = l; i <= r; i++) {
    //     if (a[i] != fi && a[i] > se) {
    //         se = a[i];
    //         x = i;
    //     }
    // }
    // return x;
}

int n, p, ans;
void dfs(int l, int r) {
    if (r - l == 1) {
        ans = l + r - p;
        return;
    }
    if (r - l == 2) {
        if (p == l) {
            int q = ask(l + 1, r);
            ans = l + 1 + r - q;
        } else if (p == r) {
            int q = ask(l, l + 1);
            ans = l + l + 1 - q;
        } else {
            int q = ask(l, l + 1);
            if (p == q) {
                ans = l;
            } else {
                ans = r;
            }
        }
        return;
    }

    int len23 = (r - l + 1) * 0.6;
    if (p <= l + len23 - 1) {
        int q = ask(l, l + len23 - 1);
        if (p == q) {
            dfs(l, l + len23 - 1);
        } else {
            p = ask(l + len23, r);
            dfs(l + len23, r);
        }
    } else {
        int q = ask(r - len23 + 1, r);
        if (p == q) {
            dfs(r - len23 + 1, r);
        } else {
            p = ask(l, r - len23);
            dfs(l, r - len23);
        }
    }

}

void solve() {
    cin >> n;
    p = ask(1, n);
    dfs(1, n);
    cout << '!' << ' ' << ans << endl;
}

int main() {
    ios_base::sync_with_stdio(false);

    int tt;
    cin >> tt;
    while (tt--) solve();

    return 0;
}
源文件, 语言: C++14

详细

Test #1:

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

input:

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

output:

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

result:

ok Correct (3 test cases)

Test #2:

score: 0
Accepted
time: 62ms
memory: 3668kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #3:

score: 0
Accepted
time: 55ms
memory: 3656kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #4:

score: 0
Accepted
time: 73ms
memory: 3652kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #5:

score: 0
Accepted
time: 115ms
memory: 3656kb

input:

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

output:

? 1 100
? 1 60
? 61 100
? 61 84
? 61 74
? 61 68
? 69 74
? 69 71
? 69 70
! 70
? 1 9
? 1 5
? 1 3
? 1 2
! 3
? 1 53
? 23 53
? 1 22
? 1 13
? 1 7
? 4 7
? 6 7
? 4 5
! 5
? 1 33
? 1 19
? 20 33
? 26 33
? 30 33
? 30 31
? 32 33
! 33
? 1 82
? 34 82
? 1 33
? 15 33
? 23 33
? 28 33
? 23 27
? 23 25
? 24 25
! 25
? 1 ...

result:

ok Correct (10000 test cases)

Test #6:

score: 0
Accepted
time: 86ms
memory: 3780kb

input:

10000
50
10
10
10
10
6
2
1
3
50
11
11
9
23
23
23
22
25
50
44
44
40
21
21
21
22
23
50
24
14
45
45
40
49
48
46
50
50
50
50
50
50
49
47
45
50
36
23
17
17
18
12
11
10
50
29
29
20
3
3
3
3
50
30
30
22
1
1
1
2
4
50
25
25
25
25
21
30
29
27
50
18
20
49
47
37
37
37
50
9
9
9
5
17
18
14
13
11
50
26
26
26
28
17
...

output:

? 1 50
? 1 30
? 1 18
? 1 10
? 5 10
? 1 4
? 1 2
? 3 4
! 4
? 1 50
? 1 30
? 1 18
? 19 30
? 19 25
? 22 25
? 22 23
? 24 25
! 24
? 1 50
? 21 50
? 33 50
? 21 32
? 21 27
? 21 24
? 21 22
? 23 24
! 24
? 1 50
? 1 30
? 31 50
? 39 50
? 39 45
? 46 50
? 48 50
? 46 47
! 47
? 1 50
? 21 50
? 33 50
? 41 50
? 45 50
? 4...

result:

ok Correct (10000 test cases)

Test #7:

score: 0
Accepted
time: 108ms
memory: 3668kb

input:

10000
100
76
49
35
34
5
3
11
11
11
100
29
29
29
29
29
29
30
26
26
100
64
64
69
88
88
86
78
77
80
81
100
51
57
98
98
92
79
79
77
81
80
100
44
44
50
13
13
13
12
9
10
7
100
64
92
22
19
27
25
40
40
39
37
100
93
93
86
56
59
44
44
44
45
100
37
2
97
81
76
76
74
68
68
100
76
76
58
94
95
80
79
86
85
83
100
3...

output:

? 1 100
? 41 100
? 1 40
? 17 40
? 1 16
? 1 9
? 10 16
? 10 13
? 10 11
! 10
? 1 100
? 1 60
? 1 36
? 16 36
? 25 36
? 25 31
? 28 31
? 25 27
? 25 26
! 25
? 1 100
? 41 100
? 41 76
? 77 100
? 77 90
? 83 90
? 77 82
? 77 79
? 80 82
? 81 82
! 82
? 1 100
? 1 60
? 61 100
? 77 100
? 87 100
? 77 86
? 77 82
? 77 7...

result:

ok Correct (10000 test cases)

Test #8:

score: 0
Accepted
time: 26ms
memory: 3860kb

input:

1000
1000
475
426
728
747
896
896
896
867
841
841
841
844
847
845
1000
278
17
974
811
757
751
637
618
664
652
639
639
640
642
643
1000
75
128
871
985
607
644
713
732
749
749
742
735
737
739
738
1000
239
239
45
577
577
520
458
458
458
458
459
467
466
465
1000
978
978
978
978
978
978
997
944
950
932
9...

output:

? 1 1000
? 1 600
? 601 1000
? 601 840
? 841 1000
? 841 936
? 841 897
? 864 897
? 841 863
? 841 853
? 841 847
? 841 844
? 845 847
? 845 846
! 846
? 1 1000
? 1 600
? 601 1000
? 761 1000
? 601 760
? 665 760
? 601 664
? 601 638
? 639 664
? 650 664
? 639 649
? 639 644
? 639 641
? 642 644
? 643 644
! 644
...

result:

ok Correct (1000 test cases)

Test #9:

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

input:

1017
272
246
111
27
52
73
73
73
73
73
73
72
114
105
91
2
2
2
2
2
2
2
910
173
173
173
173
127
14
29
65
65
56
51
51
50
48
726
229
229
229
201
63
63
28
17
17
13
24
24
26
861
315
104
671
671
688
593
593
593
593
593
593
593
594
1984
133
133
133
406
571
512
704
704
701
673
658
650
650
652
647
646
1145
988...

output:

? 1 272
? 110 272
? 1 109
? 1 65
? 66 109
? 66 91
? 66 80
? 66 74
? 70 74
? 72 74
? 72 73
! 74
? 1 114
? 47 114
? 1 46
? 1 27
? 1 16
? 1 9
? 1 5
? 1 3
? 1 2
! 1
? 1 910
? 1 546
? 1 327
? 1 196
? 80 196
? 1 79
? 1 47
? 48 79
? 48 66
? 56 66
? 48 55
? 48 51
? 50 51
? 48 49
! 49
? 1 726
? 1 435
? 1 261...

result:

ok Correct (1017 test cases)

Test #10:

score: 0
Accepted
time: 3ms
memory: 3784kb

input:

10
100000
3893
3893
30673
43582
43582
43582
43582
43582
43582
43582
43582
43582
43470
43242
43242
43242
43245
43268
43263
43279
43278
43273
43272
43270
100000
32066
54928
68197
71764
88585
88585
85554
93282
93282
93193
91599
91599
91599
91474
91415
91415
91410
91370
91365
91355
91355
91354
91351
913...

output:

? 1 100000
? 1 60000
? 1 36000
? 36001 60000
? 36001 50400
? 36001 44640
? 39457 44640
? 41531 44640
? 42775 44640
? 42775 43893
? 43223 43893
? 43223 43624
? 43384 43624
? 43223 43383
? 43223 43318
? 43223 43279
? 43223 43256
? 43257 43279
? 43257 43269
? 43270 43279
? 43274 43279
? 43270 43273
? 4...

result:

ok Correct (10 test cases)

Test #11:

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

input:

21
84335
47947
47947
22445
9296
1509
19830
19830
19815
17079
17079
17079
17079
17084
17217
17221
17316
17316
17316
17308
17320
17320
17318
17323
17321
159962
128177
145530
35270
7423
54814
49869
40850
40850
38954
42103
43214
43823
43823
43823
43823
43896
43765
43753
43695
43695
43695
43695
43695
436...

output:

? 1 84335
? 1 50601
? 20242 50601
? 1 20241
? 1 12144
? 12145 20241
? 15384 20241
? 17328 20241
? 15384 17327
? 16162 17327
? 16629 17327
? 16909 17327
? 16909 17159
? 17160 17327
? 17160 17259
? 17260 17327
? 17288 17327
? 17304 17327
? 17304 17317
? 17318 17327
? 17318 17323
? 17318 17320
? 17321 ...

result:

ok Correct (21 test cases)

Test #12:

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

input:

1
1000000
641602
641602
418256
783270
783270
783270
783270
786055
805651
802269
794273
791414
797591
797591
797004
796734
796734
796734
796686
796850
796850
796850
796844
796864
796864
796864
796866
796861
796863

output:

? 1 1000000
? 400001 1000000
? 400001 760000
? 760001 1000000
? 760001 904000
? 760001 846400
? 760001 811840
? 760001 791104
? 791105 811840
? 799400 811840
? 791105 799399
? 791105 796081
? 796082 799399
? 796082 798071
? 796878 798071
? 796082 796877
? 796401 796877
? 796592 796877
? 796592 79676...

result:

ok Correct (1 test case)

Test #13:

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

input:

16
232936
229707
229707
229707
229707
229707
229707
229707
231039
223556
224031
225790
225790
225790
225915
225474
225474
225483
225375
225407
225417
225419
225431
225430
225425
225425
8676
6498
6498
6498
4978
3906
3959
4684
4684
4684
4684
4684
4684
4684
4676
4692
4692
4691
4695
221085
172303
209705...

output:

? 1 232936
? 93176 232936
? 149081 232936
? 182624 232936
? 202750 232936
? 214825 232936
? 222070 232936
? 226417 232936
? 222070 226416
? 222070 224677
? 224678 226416
? 225374 226416
? 225374 225998
? 225624 225998
? 225374 225623
? 225374 225523
? 225434 225523
? 225374 225433
? 225374 225409
? ...

result:

ok Correct (16 test cases)

Test #14:

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

input:

1994
667
666
667
267
266
107
106
43
42
18
17
8
7
4
3
2
374
373
374
150
149
60
59
24
23
10
9
4
3
2
488
486
488
196
195
79
78
32
31
13
12
6
5
3
2
922
921
922
369
368
148
147
60
59
24
23
10
9
4
3
2
639
637
639
256
255
103
102
42
41
17
16
7
6
3
2
353
350
353
142
141
57
56
23
22
10
9
4
3
2
71
66
71
29
28...

output:

? 1 667
? 268 667
? 1 267
? 108 267
? 1 107
? 44 107
? 1 43
? 19 43
? 1 18
? 9 18
? 1 8
? 5 8
? 1 4
? 3 4
? 1 2
! 1
? 1 374
? 151 374
? 1 150
? 61 150
? 1 60
? 25 60
? 1 24
? 11 24
? 1 10
? 5 10
? 1 4
? 3 4
? 1 2
! 1
? 1 488
? 197 488
? 1 196
? 80 196
? 1 79
? 33 79
? 1 32
? 14 32
? 1 13
? 7 13
? 1 ...

result:

ok Correct (1994 test cases)

Test #15:

score: 0
Accepted
time: 3ms
memory: 3788kb

input:

18
153667
153667
153666
61467
61466
24587
24586
9835
9834
3934
3933
1574
1573
630
629
252
251
101
100
41
40
17
16
7
6
3
2
211376
211374
211376
84551
84550
33821
33820
13529
13528
5412
5411
2165
2164
866
865
347
346
139
138
56
55
23
22
10
9
4
3
2
195330
195326
195330
78132
78131
31253
31252
12502
125...

output:

? 1 153667
? 61468 153667
? 1 61467
? 24588 61467
? 1 24587
? 9836 24587
? 1 9835
? 3935 9835
? 1 3934
? 1575 3934
? 1 1574
? 631 1574
? 1 630
? 253 630
? 1 252
? 102 252
? 1 101
? 42 101
? 1 41
? 18 41
? 1 17
? 8 17
? 1 7
? 4 7
? 1 3
? 1 2
! 1
? 1 211376
? 84552 211376
? 1 84551
? 33822 84551
? 1 3...

result:

ok Correct (18 test cases)

Test #16:

score: -100
Wrong Answer
time: 1ms
memory: 3656kb

input:

1
1000000
999998
1000000
400000
399999
160000
159999
64000
63999
25600
25599
10240
10239
4096
4095
1639
1638
656
655
263
262
106
105
43
42
18
17
8
7
4
3

output:

? 1 1000000
? 400001 1000000
? 1 400000
? 160001 400000
? 1 160000
? 64001 160000
? 1 64000
? 25601 64000
? 1 25600
? 10241 25600
? 1 10240
? 4097 10240
? 1 4096
? 1640 4096
? 1 1639
? 657 1639
? 1 656
? 264 656
? 1 263
? 107 263
? 1 106
? 44 106
? 1 43
? 19 43
? 1 18
? 9 18
? 1 8
? 5 8
? 1 4
? 3 4
...

result:

wrong answer Too many queries , n = 1000000 , now_q 31 (test case 1)
English 繁體中文 简体中文

服务器时间: 2025-02-09 02:04:27 | 开源项目