QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#607467#8939. PermutationUESTC_Snow_Halation#RE 101ms10272kbC++142.7kb2024-10-03 14:59:322024-10-03 14:59:32

Judging History

This is the latest submission verdict.

  • [2024-10-03 14:59:32]
  • Judged
  • Verdict: RE
  • Time: 101ms
  • Memory: 10272kb
Show
  • [2024-10-03 14:59:32]
  • Submitted

answer

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define FOR() ll le=e[u].size();for(ll i=0;i<le;i++)
#define QWQ cout<<"QwQ\n";
#define ll long long
#include <vector>
#include <queue>
#include <map>

using namespace std;
const ll N=1201010;
const ll qwq=303030;
const ll inf=0x3f3f3f3f;

inline ll read() {
    ll sum = 0, ff = 1; char c = getchar();
    while(c<'0' || c>'9') { if(c=='-') ff = -1; c = getchar(); }
    while(c>='0'&&c<='9') { sum = sum * 10 + c - '0'; c = getchar(); }
    return sum * ff;
}

int T,n;
int f[N],fen[N];
int ans;
int cnt = 0;

void ask(int l,int r) {
    cnt++;
    if(cnt>(ll)ceil((double)(1.5*log2(n)))) cout<<cnt/0;
    cout<<"? "<<l<<" "<<r<<"\n";
    fflush(stdout);
}

void DFS(int cl,int wei,int l,int r) {
    int len = r-l+1;

    if(len<=1) { cout<<wei/0; }

    if(len==2) {
        ask(l,r);
        int xia = read();
        if(xia==l) ans = r;
        else       ans = l;
        return ;
    }

    if(cl==0) {
        ask(l,r);
        wei = read();
    }

    if(len==3) {
        if(wei==l) {
            ask(l,l+1);
            int xia = read();
            if(xia==l) ans = l+1;
            else       ans = r;
        }
        else if(wei==l+1) {
            ask(l,l+1);
            int xia = read();
            if(xia==l) ans = r;
            else       ans = l;
        }
        else {
            ask(l+1,r);
            int xia = read();
            if(xia==r) ans = l+1;
            else       ans = l;
        }
        return ;
    }


    int mid = l+fen[len]-1;
    if(wei<=mid) {
        ask(l,mid);
        int xia = read();
        if(xia==wei) DFS(1,wei,l,mid);
        else         DFS(0,0,mid+1,r);
    }
    else {
        mid = r-fen[len]+1;
        ask(mid,r);
        int xia = read();
        if(xia==wei) DFS(1,wei,mid,r);
        else         DFS(0,0,l,mid-1);
    }
}

int main() {
    f[1] = inf;
    f[2] = 1; fen[2] = 1;
    f[3] = 1; fen[3] = 1;
    f[4] = 2; fen[4] = 2;
    f[5] = 3; fen[5] = 3;
    for(int i=6;i<=3000;i++) {
        f[i] = inf;
        int mid = (i+1)/2;
        for(int j=mid;j<=i-1;j++) {
            int need = max(f[j]+1,f[i-j]+1+1);
            if(need < f[i]) f[i] = need, fen[i] = j;
        }
        // if(i<=1000) cout<<i<<" f = "<<f[i]<<" fen = "<<fen[i]<<"\n";
    }
    for(int i=3001;i<=N-10;i++) fen[i] = i/2;

    T = read();
    while(T--) {
        n = read();
        cnt = 0;
        DFS(0,0,1,n);
        cout<<"! "<<ans<<"\n";
        fflush(stdout);
    }
    return 0;
}

/*

3
2 3
1 2
2 2
4 5 100

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

*/
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 9720kb

input:

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

output:

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

result:

ok Correct (3 test cases)

Test #2:

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

input:

10000
10
2
2
3
5
5
10
10
10
8
5
5
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
8
10
2
4
9
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
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
10
1
3
8
8
8
10
7
9
4
4
4
10
7
8
4
4
4
10
3
4
7
8
10
10
4...

output:

? 1 10
? 1 6
? 1 3
? 4 6
? 4 5
! 4
? 1 10
? 5 10
? 8 10
? 5 7
? 5 6
! 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
? 2 3
! 1
? 1 10
? 1 6
? 7 10
? 9 10
? 7 8
! 8
? 1 10
? 1 6
? 7 10
? 7 8
? 7 8
! 7
? 1 10
? 1 6
? 7 1...

result:

ok Correct (10000 test cases)

Test #3:

score: 0
Accepted
time: 40ms
memory: 8864kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #4:

score: 0
Accepted
time: 101ms
memory: 9088kb

input:

10000
47
23
23
24
11
9
2
1
3
14
8
8
8
9
11
25
6
6
4
13
13
13
13
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
7
5
3
3
22
6
4
14
12
20
19
21
34
29
25
17
17
17
17
16
42
20
20
20
20
20
21
19
47
21
21
21
21
21
19
16
17
41
25
25
30
33
33
34
36
35
19
17
17
16
12
13
10
21
14
14
14...

output:

? 1 47
? 1 29
? 12 29
? 1 11
? 5 11
? 1 4
? 1 2
? 3 4
! 4
? 1 14
? 8 14
? 8 11
? 8 9
? 10 11
! 10
? 1 25
? 1 14
? 1 7
? 8 14
? 11 14
? 13 14
? 13 14
! 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 11
? 1 7
? 4 7
? 6 ...

result:

ok Correct (10000 test cases)

Test #5:

score: 0
Accepted
time: 101ms
memory: 8752kb

input:

10000
100
47
5
61
61
61
62
71
71
71
71
9
2
2
2
1
53
46
35
6
6
6
6
6
6
33
3
16
31
31
31
29
32
82
60
42
29
29
29
29
28
26
26
88
39
8
59
59
59
59
59
59
59
71
24
29
59
44
65
65
64
61
61
92
52
52
70
88
88
85
89
89
89
24
11
11
9
5
5
5
66
51
51
66
45
45
45
44
43
42
92
43
43
38
12
12
8
17
17
17
48
1
1
1
5
9...

output:

? 1 100
? 1 53
? 54 100
? 54 82
? 54 71
? 54 64
? 65 71
? 68 71
? 70 71
? 70 71
! 70
? 1 9
? 1 5
? 1 3
? 1 2
! 3
? 1 53
? 27 53
? 1 26
? 1 15
? 1 8
? 5 8
? 5 6
? 5 6
! 5
? 1 33
? 1 17
? 18 33
? 25 33
? 29 33
? 29 31
? 32 33
! 33
? 1 82
? 42 82
? 1 41
? 19 41
? 19 30
? 25 30
? 28 30
? 25 27
? 25 26
!...

result:

ok Correct (10000 test cases)

Test #6:

score: 0
Accepted
time: 96ms
memory: 10184kb

input:

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

output:

? 1 50
? 1 25
? 1 14
? 8 14
? 1 7
? 1 4
? 1 2
? 3 4
! 4
? 1 50
? 1 25
? 1 14
? 15 25
? 15 21
? 22 25
? 22 23
? 24 25
! 24
? 1 50
? 26 50
? 1 25
? 1 14
? 15 25
? 15 21
? 22 25
? 24 25
? 24 25
! 24
? 1 50
? 1 25
? 26 50
? 37 50
? 44 50
? 44 47
? 44 45
? 46 47
! 47
? 1 50
? 26 50
? 37 50
? 44 50
? 47 5...

result:

ok Correct (10000 test cases)

Test #7:

score: 0
Accepted
time: 89ms
memory: 9924kb

input:

10000
100
76
49
35
44
5
5
3
9
8
11
100
29
29
50
20
20
20
22
26
26
26
100
64
64
69
88
88
88
86
84
85
83
100
51
15
57
57
63
79
79
77
81
80
100
44
44
50
13
13
13
12
11
10
9
100
64
92
22
19
41
41
41
42
39
39
100
93
56
40
40
40
32
44
41
45
45
100
37
2
97
81
57
54
68
67
70
70
100
76
76
76
76
74
86
86
85
8...

output:

? 1 100
? 48 100
? 1 47
? 19 47
? 1 18
? 1 11
? 1 7
? 8 11
? 8 9
? 10 11
! 10
? 1 100
? 1 53
? 27 53
? 1 26
? 12 26
? 19 26
? 19 22
? 23 26
? 25 26
? 25 26
! 25
? 1 100
? 48 100
? 48 74
? 75 100
? 75 89
? 82 89
? 86 89
? 82 85
? 84 85
? 82 83
! 82
? 1 100
? 1 53
? 54 100
? 54 82
? 54 71
? 72 82
? 76...

result:

ok Correct (10000 test cases)

Test #8:

score: 0
Accepted
time: 29ms
memory: 9208kb

input:

1000
1000
475
426
728
747
896
896
867
831
831
828
841
844
847
848
845
1000
278
17
974
811
598
534
679
689
637
628
652
647
645
645
645
1000
75
128
871
871
871
842
713
713
712
732
730
742
742
743
741
1000
239
239
45
432
432
442
458
458
458
458
459
462
461
463
1000
978
978
978
978
978
997
914
914
902
9...

output:

? 1 1000
? 1 500
? 501 1000
? 501 801
? 802 1000
? 802 924
? 849 924
? 802 848
? 820 848
? 820 837
? 838 848
? 838 844
? 845 848
? 847 848
? 845 846
! 846
? 1 1000
? 1 500
? 501 1000
? 700 1000
? 501 699
? 501 623
? 624 699
? 653 699
? 624 652
? 624 641
? 642 652
? 646 652
? 642 645
? 644 645
? 644 ...

result:

ok Correct (1000 test cases)

Test #9:

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

input:

1017
272
246
186
27
27
15
73
73
73
73
71
75
75
114
105
91
2
2
2
2
2
2
2
2
910
173
173
173
127
14
14
29
65
65
56
51
51
50
48
726
229
229
201
186
118
63
39
28
28
28
28
29
24
23
861
315
104
671
688
491
551
593
593
593
593
586
597
597
598
596
1984
133
133
406
863
863
869
724
704
650
650
650
650
650
652
...

output:

? 1 272
? 124 272
? 1 123
? 1 76
? 1 47
? 48 76
? 59 76
? 66 76
? 70 76
? 70 73
? 74 76
? 74 75
! 74
? 1 114
? 48 114
? 1 47
? 1 29
? 1 18
? 1 11
? 1 7
? 1 4
? 1 2
? 1 2
! 1
? 1 910
? 1 455
? 1 256
? 124 256
? 1 123
? 1 76
? 1 47
? 48 76
? 48 65
? 55 65
? 48 54
? 48 51
? 50 51
? 48 49
! 49
? 1 726
?...

result:

ok Correct (1017 test cases)

Test #10:

score: -100
Runtime Error

input:

10
100000
3893
3893
3505
30673
33920
43582
43582
43582
43582
43582
43470
43242
43242
43242
43197
43289
43289
43279
43268
43263
43273
43272
43270
100000
32066
19090
54928
68197
88585
88585
88585
89959
93282
93193
91599
91474
90979
90917
91257
91159
91398
91398
91383
91339
91348
91355
91355
91355
91354

output:

? 1 100000
? 1 50000
? 1 25000
? 25001 50000
? 25001 37500
? 37501 50000
? 37501 43750
? 40626 43750
? 42189 43750
? 42970 43750
? 43292 43750
? 42970 43291
? 43093 43291
? 43169 43291
? 43169 43244
? 43245 43291
? 43263 43291
? 43274 43291
? 43263 43273
? 43263 43269
? 43270 43273
? 43272 43273
? 4...

result:
English 繁體中文 简体中文

Server Time: 2025-02-09 08:06:07 | OpenSource Project