QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#765275#8267. Staring Contest_8_8_#9 3ms7812kbC++201.6kb2024-11-20 13:32:262024-11-20 13:32:26

Judging History

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

  • [2024-11-20 13:32:26]
  • 评测
  • 测评结果:9
  • 用时:3ms
  • 内存:7812kb
  • [2024-11-20 13:32:26]
  • 提交

answer

#include <bits/stdc++.h> 

using namespace std;

typedef long long ll;

const int N = (int)1e6 + 12;

const ll inf = (ll)1e18;

int c = 0;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// mt19937 rng(123121);
int n, p, res[N], a[N];
bool loc = 0;
int get(int i, int j) {
    c++;
    assert(c <= 3000);
    cout << "? " << i << ' ' << j << endl;
    if(loc) return min(a[i], a[j]);
    int x;
    cin >> x;
    return x;
}
void solve(vector<int> &x) {
    if((int)x.size() <= 1) return;
    p = x[rng()%(int)x.size()];
    vector<pair<int, int>> e;
    for(int i : x) if(i != p) {
        e.emplace_back(get(i, p) , i);
    }
    sort(e.begin(), e.end());
    int f = -1;
    // cout << p << '\n';
    // for(auto [x, y] : e) {
    //     cout << x << ' ' << y << '\n';
    // }
    res[p] = e.back().first;
    vector<int> t;
    for(int i = 0; i < (int)e.size(); i++) {
        if(e[i].first == e.back().first) {
            t.push_back(e[i].second);
        } else {
            res[e[i].second] = e[i].first;
        }
    }
    if((int)t.size() == 1) {
        res[t[0]] = e.back().first;
    }
    solve(t);
}
void test() {
    cin >> n;
    if(loc) {
        for(int i = 1; i <= n; i++) {
            cin >> a[i];
        }
    }
    vector<int> f(n);
    iota(f.begin(), f.end(), 1);
    solve(f);

    cout << "! ";
    for(int i = 1; i <= n; i++) {
        cout << res[i] << ' ';
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t = 1;
    // cin >> t;

    while(t--) 
        test();

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 9
Accepted

Test #1:

score: 9
Accepted
time: 1ms
memory: 5692kb

input:

2
1

output:

? 1 2
! 1 1 

result:

points 1.0 points  1.0 n = 2, you used 1 queries

Test #2:

score: 9
Accepted
time: 1ms
memory: 5660kb

input:

2
1

output:

? 2 1
! 1 1 

result:

points 1.0 points  1.0 n = 2, you used 1 queries

Test #3:

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

input:

2
1

output:

? 2 1
! 1 1 

result:

points 1.0 points  1.0 n = 2, you used 1 queries

Test #4:

score: 9
Accepted
time: 1ms
memory: 5748kb

input:

50
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
45
45
45
45
46
47
48
49

output:

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

result:

points 1.0 points  1.0 n = 50, you used 53 queries

Test #5:

score: 9
Accepted
time: 1ms
memory: 5932kb

input:

50
33
33
33
33
33
33
33
33
33
33
33
33
33
33
33
33
33
32
31
30
29
28
27
26
25
24
23
22
21
20
19
18
17
16
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
37
37
37
37
37
37
37
37
37
37
37
37
37
36
35
34
39
39
39
39
39
39
39
39
39
39
39
38
49
48
47
46
45
44
43
42
41
40

output:

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

result:

points 1.0 points  1.0 n = 50, you used 87 queries

Test #6:

score: 9
Accepted
time: 1ms
memory: 5888kb

input:

50
1
3
5
7
9
11
13
15
17
19
21
23
25
27
29
31
33
35
37
39
41
43
45
46
46
46
46
44
42
40
38
36
34
32
30
28
26
24
22
20
18
16
14
12
10
8
6
4
2
47
47
47
48
48
49

output:

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

result:

points 1.0 points  1.0 n = 50, you used 55 queries

Test #7:

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

input:

50
2
4
6
8
10
12
14
16
18
20
22
24
26
26
26
26
26
26
26
26
26
26
26
26
26
26
26
26
26
26
26
26
26
26
26
26
25
23
21
19
17
15
13
11
9
7
5
3
1
28
30
32
34
36
38
39
39
39
39
39
39
39
39
39
39
39
37
35
33
31
29
27
40
42
44
46
48
49
47
45
43
41

output:

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

result:

points 1.0 points  1.0 n = 50, you used 82 queries

Test #8:

score: 9
Accepted
time: 1ms
memory: 5748kb

input:

50
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
8
6
4
2
1
3
5
7
9
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
37
37
37
37
37
37
37
36
34
32
30
28
26
24
22
20
18
16
14
12
11
13
15
17
19
21
23
25
27
29
31
33
35
37
37
37
37
37
37
46
46
44
42
40
38
39
41
43
45
46
46
48
47
49

output:

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

result:

points 1.0 points  1.0 n = 50, you used 103 queries

Test #9:

score: 9
Accepted
time: 1ms
memory: 5636kb

input:

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

output:

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

result:

points 1.0 points  1.0 n = 50, you used 113 queries

Test #10:

score: 9
Accepted
time: 1ms
memory: 5696kb

input:

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

output:

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

result:

points 1.0 points  1.0 n = 50, you used 152 queries

Test #11:

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

input:

50
39
1
39
2
39
3
39
4
39
5
39
6
39
7
39
8
39
9
39
10
39
11
12
38
13
37
14
36
15
35
16
34
17
33
18
32
19
31
20
30
21
29
22
28
23
27
24
26
25
43
43
43
43
43
43
43
42
41
40
46
46
46
46
45
44
49
48
47

output:

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

result:

points 1.0 points  1.0 n = 50, you used 68 queries

Test #12:

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

input:

50
1
3
2
5
4
7
6
9
8
11
10
13
12
15
14
17
16
19
18
21
20
23
22
25
24
27
26
29
28
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
31
33
32
34
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
37
36
39
38
41
40
43
42
44
45
45
45
45
45
47
46
48
49

output:

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

result:

points 1.0 points  1.0 n = 50, you used 86 queries

Test #13:

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

input:

50
36
36
36
36
36
36
36
36
36
36
36
36
36
36
34
35
32
33
30
31
28
29
26
27
24
25
22
23
20
21
18
19
16
17
14
15
12
13
10
11
8
9
6
7
4
5
2
3
1
48
49
46
47
44
45
42
43
40
41
38
39
37

output:

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

result:

points 1.0 points  1.0 n = 50, you used 62 queries

Test #14:

score: 9
Accepted
time: 1ms
memory: 5756kb

input:

50
2
20
20
20
20
20
20
20
20
20
8
12
20
10
20
20
20
20
20
17
20
20
1
7
20
20
20
19
20
20
4
16
9
11
14
20
18
20
20
20
13
15
20
20
20
5
3
20
6
39
28
45
30
47
22
36
46
48
44
34
42
43
32
26
49
31
23
41
40
29
38
33
25
21
24
37
35
27

output:

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

result:

points 1.0 points  1.0 n = 50, you used 78 queries

Test #15:

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

input:

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

output:

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

result:

points 1.0 points  1.0 n = 10, you used 19 queries

Test #16:

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

input:

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

output:

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

result:

points 1.0 points  1.0 n = 10, you used 11 queries

Test #17:

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

input:

50
7
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
9
10
11
14
15
17
18
19
29
32
33
35
38
40
44
45
49
53
54
55
57
58
59
62
64
65
67
68
70
71
72
74
76
77
77
77
77
77
77
77
77
77
77
77
77
77
77
79
80
82
84
86
86
86
86
86
86
86
86
86
87
90
91
93
95
96
97...

output:

? 1 2
? 3 2
? 4 2
? 5 2
? 6 2
? 7 2
? 8 2
? 9 2
? 10 2
? 11 2
? 12 2
? 13 2
? 14 2
? 15 2
? 16 2
? 17 2
? 18 2
? 19 2
? 20 2
? 21 2
? 22 2
? 23 2
? 24 2
? 25 2
? 26 2
? 27 2
? 28 2
? 29 2
? 30 2
? 31 2
? 32 2
? 33 2
? 34 2
? 35 2
? 36 2
? 37 2
? 38 2
? 39 2
? 40 2
? 41 2
? 42 2
? 43 2
? 44 2
? 45 2
...

result:

points 1.0 points  1.0 n = 50, you used 117 queries

Test #18:

score: 9
Accepted
time: 1ms
memory: 5596kb

input:

50
86350
86351
86352
86353
86354
86355
86356
86357
86358
86359
86359
86359
86359
86359
86359
86359
86359
86359
86359
86359
86359
86359
86359
86359
86359
86359
86359
86359
86359
86359
86359
86359
86359
86359
86359
86359
86359
86359
86359
86359
86359
86359
86359
86359
86359
86359
86359
86359
86359
863...

output:

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

result:

points 1.0 points  1.0 n = 50, you used 124 queries

Test #19:

score: 9
Accepted
time: 1ms
memory: 5684kb

input:

50
5076
5302
5406
5454
5703
5773
5813
5914
6099
6109
6297
6375
6476
6651
6767
6767
6767
6767
6767
6767
6767
6767
6767
6767
6767
6767
6767
6767
6767
6767
6767
6767
6767
6767
6767
6767
6767
6767
6767
6767
6767
6767
6767
6767
6767
6767
6767
6767
6767
6824
6926
7026
7060
7159
7174
7233
7560
7563
7663
77...

output:

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

result:

points 1.0 points  1.0 n = 50, you used 89 queries

Test #20:

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

input:

50
5000
5003
5004
5005
5010
5017
5021
5023
5024
5025
5027
5029
5030
5031
5033
5035
5036
5038
5039
5041
5046
5048
5049
5050
5051
5052
5054
5058
5059
5062
5064
5065
5066
5066
5066
5066
5066
5066
5066
5066
5066
5066
5066
5066
5066
5066
5066
5066
5066
5068
5069
5072
5073
5075
5076
5078
5081
5082
5082
50...

output:

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

result:

points 1.0 points  1.0 n = 50, you used 72 queries

Test #21:

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

input:

50
50293
50918
51290
52391
52428
52604
53250
54556
54962
56134
56501
56991
57154
57364
58019
58109
59551
60767
61154
62431
65062
66090
66780
67289
67305
67305
67305
67305
67305
67305
67305
67305
67305
67305
67305
67305
67305
67305
67305
67305
67305
67305
67305
67305
67305
67305
67305
67305
67305
676...

output:

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

result:

points 1.0 points  1.0 n = 50, you used 106 queries

Test #22:

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

input:

50
29
16
13
10
15
28
18
29
12
29
14
29
17
11
3
27
6
20
4
29
29
9
29
29
29
29
29
29
25
8
29
29
29
19
24
29
29
29
7
5
1
29
2
29
23
22
29
21
26
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
33
33
31
33
33
33
33
33
33
33
33
33
33
33
33
32
33
33
33
35
35
35
35
35
34
35
35
35
35
35
35
35
35
...

output:

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

result:

points 1.0 points  1.0 n = 50, you used 118 queries

Test #23:

score: 9
Accepted
time: 1ms
memory: 5632kb

input:

50
36
42
58
10
58
58
41
6
46
58
3
39
58
25
14
29
58
58
17
55
58
58
58
52
58
56
2
58
9
31
58
58
7
15
58
58
5
58
58
49
58
11
58
20
58
26
58
38
58
88
86
66
79
85
72
73
88
78
88
88
67
88
68
80
70
88
75
69
88
88
88
90
95
89
91
94
95
95
95
96
96
96
97
97
98

output:

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

result:

points 1.0 points  1.0 n = 50, you used 85 queries

Test #24:

score: 9
Accepted
time: 1ms
memory: 5924kb

input:

50
86374
86362
86357
86374
86374
86374
86374
86374
86369
86365
86374
86370
86350
86374
86361
86374
86356
86374
86374
86374
86374
86374
86374
86374
86374
86358
86368
86351
86374
86355
86374
86363
86360
86374
86371
86373
86374
86366
86364
86359
86372
86354
86367
86374
86374
86374
86353
86374
86352
863...

output:

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

result:

points 1.0 points  1.0 n = 50, you used 74 queries

Test #25:

score: 9
Accepted
time: 1ms
memory: 5696kb

input:

50
5118
6181
5299
6181
6181
6181
5144
6181
6181
6181
5252
6181
6181
6181
6181
6181
6181
5529
6181
6181
6181
6181
5271
6181
6181
6181
6181
5503
6181
6181
6181
6181
6181
6181
5603
5141
6181
6181
6181
6181
6181
6181
6181
5310
6051
6181
6181
5907
5171
7960
7960
6461
7960
6553
6786
7215
6722
7960
7960
79...

output:

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

result:

points 1.0 points  1.0 n = 50, you used 102 queries

Test #26:

score: 9
Accepted
time: 1ms
memory: 5636kb

input:

50
5010
5047
5052
5052
5045
5052
5007
5005
5027
5019
5032
5013
5052
5042
5052
5052
5014
5052
5009
5052
5052
5049
5001
5052
5029
5002
5028
5052
5052
5033
5052
5052
5011
5024
5044
5052
5035
5025
5052
5052
5039
5052
5051
5052
5012
5052
5046
5052
5052
5078
5080
5054
5087
5058
5086
5062
5087
5087
5059
50...

output:

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

result:

points 1.0 points  1.0 n = 50, you used 75 queries

Test #27:

score: 9
Accepted
time: 1ms
memory: 5640kb

input:

50
75023
73081
75023
53987
54630
53454
75023
61401
75023
75023
73863
62990
58357
67069
72620
75023
75023
58746
75023
67146
72987
62248
70576
74971
65477
68422
75023
75023
66448
75023
75023
75023
55504
67005
51658
54250
70928
74083
75023
61968
75023
75023
72585
71272
53213
72291
58717
57318
75023
790...

output:

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

result:

points 1.0 points  1.0 n = 50, you used 69 queries

Test #28:

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

input:

50
25
25
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
2
1
39
39
26
27
28
29
30
31
32
33
34
35
36
37
38
39
39
39
39
39
39
39
39
39
49
40
41
42
43
44
45
46
47
48

output:

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

result:

points 1.0 points  1.0 n = 50, you used 83 queries

Test #29:

score: 9
Accepted
time: 1ms
memory: 5656kb

input:

50
49
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
1
2

output:

? 1 2
? 3 2
? 4 2
? 5 2
? 6 2
? 7 2
? 8 2
? 9 2
? 10 2
? 11 2
? 12 2
? 13 2
? 14 2
? 15 2
? 16 2
? 17 2
? 18 2
? 19 2
? 20 2
? 21 2
? 22 2
? 23 2
? 24 2
? 25 2
? 26 2
? 27 2
? 28 2
? 29 2
? 30 2
? 31 2
? 32 2
? 33 2
? 34 2
? 35 2
? 36 2
? 37 2
? 38 2
? 39 2
? 40 2
? 41 2
? 42 2
? 43 2
? 44 2
? 45 2
...

result:

points 1.0 points  1.0 n = 50, you used 49 queries

Test #30:

score: 9
Accepted
time: 1ms
memory: 5632kb

input:

50
26
19
29
29
10
29
28
29
11
22
29
29
6
29
29
20
29
12
14
29
29
13
29
29
25
29
9
27
24
29
3
29
29
23
29
21
2
8
15
7
1
4
17
18
5
16
29
29
29
36
36
36
33
30
35
31
36
36
36
36
36
36
36
32
36
36
34
36
36
41
43
40
39
44
37
44
38
44
42
44
44
44
48
45
47
46
49

output:

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

result:

points 1.0 points  1.0 n = 50, you used 87 queries

Test #31:

score: 9
Accepted
time: 1ms
memory: 5684kb

input:

50
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
16
16
16
16
16
16
16
16
16
16
16
16
16
16
16
16
16
16
16
16
16
16
16
16
16
16
16
16
16
16
16
16
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
41
41
41
41
41
41
41
41
42
43
44
45
46
47
48
48
49

output:

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

result:

points 1.0 points  1.0 n = 50, you used 91 queries

Test #32:

score: 9
Accepted
time: 2ms
memory: 5688kb

input:

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

output:

? 1 8
? 2 8
? 3 8
? 4 8
? 5 8
? 6 8
? 7 8
? 9 8
? 10 8
? 11 8
? 12 8
? 13 8
? 14 8
? 15 8
? 16 8
? 17 8
? 18 8
? 19 8
? 20 8
? 21 8
? 22 8
? 23 8
? 24 8
? 25 8
? 26 8
? 27 8
? 28 8
? 29 8
? 30 8
? 31 8
? 32 8
? 33 8
? 34 8
? 35 8
? 36 8
? 37 8
? 38 8
? 39 8
? 40 8
? 41 8
? 42 8
? 43 8
? 44 8
? 45 8
...

result:

points 1.0 points  1.0 n = 50, you used 154 queries

Test #33:

score: 9
Accepted
time: 2ms
memory: 7812kb

input:

50
39
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
39
39
39
39
39
39
39
39
1
39
41
40
41
41
41
41
41
41
41
41
49
42
43
44
45
46
47
48

output:

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

result:

points 1.0 points  1.0 n = 50, you used 67 queries

Test #34:

score: 9
Accepted
time: 1ms
memory: 5700kb

input:

4
2
3
3
5

output:

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

result:

points 1.0 points  1.0 n = 4, you used 4 queries

Test #35:

score: 9
Accepted
time: 1ms
memory: 5860kb

input:

4
2
3
3
5

output:

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

result:

points 1.0 points  1.0 n = 4, you used 4 queries

Test #36:

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

input:

4
2
2
2
5
3

output:

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

result:

points 1.0 points  1.0 n = 4, you used 5 queries

Test #37:

score: 9
Accepted
time: 1ms
memory: 5696kb

input:

4
2
3
3
5

output:

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

result:

points 1.0 points  1.0 n = 4, you used 4 queries

Test #38:

score: 9
Accepted
time: 1ms
memory: 5696kb

input:

4
2
5
3

output:

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

result:

points 1.0 points  1.0 n = 4, you used 3 queries

Test #39:

score: 9
Accepted
time: 1ms
memory: 5696kb

input:

4
2
2
2
5
3

output:

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

result:

points 1.0 points  1.0 n = 4, you used 5 queries

Test #40:

score: 9
Accepted
time: 1ms
memory: 5688kb

input:

4
2
2
2
3
5

output:

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

result:

points 1.0 points  1.0 n = 4, you used 5 queries

Test #41:

score: 9
Accepted
time: 1ms
memory: 5688kb

input:

4
2
3
3
5

output:

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

result:

points 1.0 points  1.0 n = 4, you used 4 queries

Test #42:

score: 9
Accepted
time: 1ms
memory: 5656kb

input:

4
2
2
2
3
5

output:

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

result:

points 1.0 points  1.0 n = 4, you used 5 queries

Test #43:

score: 9
Accepted
time: 1ms
memory: 5636kb

input:

4
3
5
2

output:

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

result:

points 1.0 points  1.0 n = 4, you used 3 queries

Test #44:

score: 9
Accepted
time: 1ms
memory: 5928kb

input:

4
3
2
3
5

output:

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

result:

points 1.0 points  1.0 n = 4, you used 4 queries

Test #45:

score: 9
Accepted
time: 1ms
memory: 5660kb

input:

4
3
5
2

output:

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

result:

points 1.0 points  1.0 n = 4, you used 3 queries

Test #46:

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

input:

4
2
3
5

output:

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

result:

points 1.0 points  1.0 n = 4, you used 3 queries

Test #47:

score: 9
Accepted
time: 1ms
memory: 5688kb

input:

4
5
2
3

output:

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

result:

points 1.0 points  1.0 n = 4, you used 3 queries

Test #48:

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

input:

4
3
2
5

output:

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

result:

points 1.0 points  1.0 n = 4, you used 3 queries

Test #49:

score: 9
Accepted
time: 1ms
memory: 5624kb

input:

4
3
5
2

output:

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

result:

points 1.0 points  1.0 n = 4, you used 3 queries

Test #50:

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

input:

4
5
2
3

output:

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

result:

points 1.0 points  1.0 n = 4, you used 3 queries

Test #51:

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

input:

4
5
3
2

output:

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

result:

points 1.0 points  1.0 n = 4, you used 3 queries

Test #52:

score: 9
Accepted
time: 1ms
memory: 5768kb

input:

4
3
2
3
5

output:

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

result:

points 1.0 points  1.0 n = 4, you used 4 queries

Test #53:

score: 9
Accepted
time: 1ms
memory: 5660kb

input:

4
2
2
2
3
3
5

output:

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

result:

points 1.0 points  1.0 n = 4, you used 6 queries

Test #54:

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

input:

4
3
2
3
5

output:

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

result:

points 1.0 points  1.0 n = 4, you used 4 queries

Test #55:

score: 9
Accepted
time: 1ms
memory: 5696kb

input:

4
2
2
2
5
3

output:

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

result:

points 1.0 points  1.0 n = 4, you used 5 queries

Test #56:

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

input:

4
5
2
3

output:

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

result:

points 1.0 points  1.0 n = 4, you used 3 queries

Test #57:

score: 9
Accepted
time: 1ms
memory: 5688kb

input:

4
5
3
2

output:

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

result:

points 1.0 points  1.0 n = 4, you used 3 queries

Subtask #2:

score: 0
Runtime Error

Test #58:

score: 0
Runtime Error

input:

1000
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101...

output:

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

result:


Subtask #3:

score: 0
Runtime Error

Test #88:

score: 30.8979
Acceptable Answer
time: 3ms
memory: 5804kb

input:

1500
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101...

output:

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

result:

points 0.38622415210 points  0.38622415210 n = 1500, you used 2944 queries

Test #89:

score: 0
Runtime Error

input:

1500
839
839
839
839
839
839
839
839
839
839
839
839
839
839
839
839
839
839
839
839
839
839
839
839
839
839
839
839
839
839
839
839
839
839
839
839
839
839
839
839
839
839
839
839
839
839
839
839
839
839
839
839
839
839
839
839
839
839
839
839
839
839
839
839
839
839
839
839
839
839
839
839
839
839...

output:

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

result: