QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#765329#8267. Staring Contest_8_8_#0 4ms5924kbC++202.4kb2024-11-20 13:54:212024-11-20 13:54:21

Judging History

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

  • [2024-11-20 13:54:21]
  • 评测
  • 测评结果:0
  • 用时:4ms
  • 内存:5924kb
  • [2024-11-20 13:54:21]
  • 提交

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;
    if((int)x.size() == 2) {
        int val = get(x[0], x[1]);
        res[x[0]] = res[x[1]] = val;
        return;
    }
    if((int)x.size() == 3) {
        int val = get(x[0], x[1]);
        int val1 = get(x[1], x[2]);
        if(val == val1) {
            res[x[1]] = val;
            solve({x[0], x[2]});
            return;
        } else {
            res[x[0]] = val;
            res[x[1]] = max(val, val1);
            res[x[2]] = val1;
        }
        return;
    }
    int m = (int)x.size();
    vector<int> nx;
    if(m & 1) {
        x.pop_back();
    }
    m--;
    vector<array<int, 3>> f;
    for(int i = 0; i < m; i += 2) {
        f.push_back({get(x[i], x[i + 1]), x[i], x[i + 1]});
    }
    array<int, 3> bf = f.back();
    f.pop_back();
    while(!f.empty()) {
        array<int, 3> nv = f.back();
        f.pop_back();
        int val = get(nv[1], bf[1]);
        if(val == nv[0]) {
            res[nv[1]] = val;
        } else if(val == bf[0]) {
            res[bf[1]] = val;
            bf = nv;
        } else {
            res[nv[2]] = nv[0];
            res[bf[2]] = bf[0];
        }
    }
    for(int i = 1; i <= n; i++) {
        if(!res[i]) {
            nx.push_back(i);
        }
    }
    solve(nx);
}
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);
    int mx = 0;
    for(int i = 1; i <= n; i++) {
        mx = max(mx ,res[i]);
    }
    for(int i =1; i <= n; i++) {
        if(!res[i]) res[i] = mx;
    }
    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: 0
Wrong Answer

Test #1:

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

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: 5684kb

input:

2
1

output:

? 1 2
! 1 1 

result:

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

Test #3:

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

input:

2
1

output:

? 1 2
! 1 1 

result:

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

Test #4:

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

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

output:

? 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
? 47 49
? 45 49
? 43 49
? 41 49
? 39 49
? 37 49
? 35 49
? 33 49
? 31 49
? 29 49
? 27 49
? 25 49
? 23 49
? 21 ...

result:

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

Test #5:

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

input:

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

output:

? 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
? 47 49
? 45 49
? 43 49
? 41 49
? 39 49
? 37 49
? 35 49
? 33 49
? 31 49
? 29 49
? 27 49
? 25 49
? 23 49
? 21 ...

result:

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

Test #6:

score: 0
Wrong Answer
time: 1ms
memory: 5888kb

input:

50
1
5
9
13
17
21
25
29
33
37
41
45
49
46
42
38
34
30
26
22
18
14
10
6
2
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
1
3
9
17
25
33
41
48
40
32
24
16
8
12
12
12
12
12
12
12
12
12
9
3
5
17
33
44
28
12
20
20
20
17
5
13
33
20
33
13
25
20
25
36
4
20
20

output:

? 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
? 47 49
? 45 49
? 43 49
? 41 49
? 39 49
? 37 49
? 35 49
? 33 49
? 31 49
? 29 49
? 27 49
? 25 49
? 23 49
? 21 ...

result:

wrong answer mismatched on more than one position

Subtask #2:

score: 0
Wrong Answer

Test #58:

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

input:

1000
1
3
5
7
9
11
13
15
17
19
21
23
25
27
29
31
33
35
37
39
41
43
45
47
49
51
53
55
57
59
61
63
65
67
69
71
73
75
77
79
81
83
85
87
89
91
93
95
97
99
101
103
105
107
109
111
113
115
117
119
121
123
125
127
129
131
133
135
137
139
141
143
145
147
149
151
153
155
157
159
161
163
165
167
169
171
173
17...

output:

? 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 ...

result:

points 1.0 points  1.0 n = 1000, you used 2006 queries

Test #59:

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

input:

1000
999
997
995
993
991
989
987
985
983
981
979
977
975
973
971
969
967
965
963
961
959
957
955
953
951
949
947
945
943
941
939
937
935
933
931
929
927
925
923
921
919
917
915
913
911
909
907
905
903
901
899
897
895
893
891
889
887
885
883
881
879
877
875
873
871
869
867
865
863
861
859
857
855
853...

output:

? 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 ...

result:

points 1.0 points  1.0 n = 1000, you used 1988 queries

Test #60:

score: 0
Wrong Answer
time: 4ms
memory: 5720kb

input:

1000
1
5
9
13
17
21
25
29
33
37
41
45
49
53
57
61
65
69
73
77
81
85
89
93
97
101
105
109
113
117
121
125
129
133
137
141
145
149
153
157
161
165
169
173
177
181
185
189
193
197
201
205
209
213
217
221
225
229
233
237
241
245
249
253
257
261
265
269
273
277
281
285
289
293
297
301
305
309
313
317
321...

output:

? 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 ...

result:

wrong answer mismatched on more than one position

Subtask #3:

score: 0
Runtime Error

Test #88:

score: 0
Runtime Error

input:

1500
1
3
5
7
9
11
13
15
17
19
21
23
25
27
29
31
33
35
37
39
41
43
45
47
49
51
53
55
57
59
61
63
65
67
69
71
73
75
77
79
81
83
85
87
89
91
93
95
97
99
101
103
105
107
109
111
113
115
117
119
121
123
125
127
129
131
133
135
137
139
141
143
145
147
149
151
153
155
157
159
161
163
165
167
169
171
173
17...

output:

? 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 ...

result: