QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#765713#8267. Staring Contest_8_8_#0 0ms12812kbC++204.2kb2024-11-20 15:04:222024-11-20 15:04:22

Judging History

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

  • [2024-11-20 15:04:22]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:12812kb
  • [2024-11-20 15:04:22]
  • 提交

answer

#include <bits/stdc++.h> 

using namespace std;

typedef long long ll;

const int N = (int)1500  + 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 mem[N][N];
int get(int i, int j) {
    if(mem[i][j] != -1) return mem[i][j];   
    c++;
    if(loc) return min(a[i], a[j]);
    cout << "? " << i << ' ' << j << endl;
    int x;
    cin >> x;
    return mem[i][j] = mem[j][i] = 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;
    }
    vector<array<int, 3>> f;
    vector<int> y;
    vector<int> vis(n + 1, 0);
    while(!x.empty()) {
        int j = x.back();
        x.pop_back();
        if(vis[j]) continue;
        bool ok = 0;
        for(int r = 0; r < (int)x.size() - 1; r++) {
            if(mem[x[r]][j] != -1) {
                f.push_back({get(x[r], j), x[r], j});
                vis[x[r]] = 1;
                ok = 1;
                break;
            }
        }
        if(!ok) {
            y.push_back(j);
        }
    }
    x = y;
    int m = (int)x.size();
    vector<int> nx;
    if(m & 1) {
        x.pop_back();
    }
    m--;
    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 {    
            if(val > max(nv[0], bf[0])) {
                res[nv[2]] = nv[0];
                res[bf[2]] = bf[0];
            }
            if(nv[0] < bf[0]) res[nv[2]] = nv[0];
            else{
                res[bf[2]] = bf[0];
                bf = nv;
            }
        }
    }
    for(int i = 1; i <= n; i++) {
        if(!res[i]) {
            nx.push_back(i);
        }
    }
    assert((int)nx.size() <= (int)x.size() / 2 + 2);
    solve(nx);
}
bool check() {
    int c = 0;
    for(int i = 1; i <= n; i++) {
        if(res[i] > a[i]) return false;
        if(res[i] < a[i]) c++;
    }
    return (c <= 1);
}
bool str = 0;
void test() {
    memset(mem, -1, sizeof(mem));
    for(int i = 1; i <= n; i++) {
        res[i] = 0;
    }
    if(!str) {
        cin >> n;
        if(loc) {
            for(int i = 1; i <= n; i++) {
                cin >> a[i];
            }
        }
    }
    vector<int> f(n);
    iota(f.begin(), f.end(), 1);
    shuffle(f.begin(), f.end(), rng);
    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;
    }
    if(!str) {
        cout << "! ";
        for(int i = 1; i <= n; i++) {
            cout << res[i] << ' ';
        }
    }
}

void stress() {
    loc = str = 1;
    for(int i = 1; i <= 100; i++) {
        n = 1500;
        for(int j = 1; j <= n; j++) {
            a[j] = j;
        }
        shuffle(a + 1, a + n + 1, rng);
        c = 0;
        test();
        cout << c << '\n';
        if(!check()) {
            for(int j = 1; j <= n; j++) {
                cout << a[j] << ' ';
            }
            cout << '\n';
            for(int j = 1; j <= n; j++) {
                cout << res[j] << ' ';
            }
            cout << '\n';
            exit(0);
        }
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
        // stress();
        // return 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
Runtime Error

Test #1:

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

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: 0ms
memory: 12772kb

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: 0ms
memory: 12812kb

input:

2
1

output:

? 2 1
! 1 1 

result:

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

Test #4:

score: 0
Runtime Error

input:

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

output:

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

result:


Subtask #2:

score: 0
Runtime Error

Test #58:

score: 0
Runtime Error

input:

1000
547
132
589
197
579
54
236
70
843
249
328
642
206
586
233
671
179
284
194
410
283
52
50
214
419
681
784
593
432
113
212
434
685
544
312
144
3
89
226
295
569
215
453
555
437
740
146
11
319
115
38
375
392
692
898
619
710
102
348
80
210
114
620
174
293
739
156
417
618
93
152
573
452
464
648
818
55...

output:

? 939 547
? 943 132
? 858 589
? 197 601
? 579 647
? 856 54
? 637 236
? 147 70
? 848 843
? 918 249
? 613 328
? 659 642
? 206 986
? 586 980
? 822 233
? 838 671
? 179 330
? 805 284
? 337 194
? 919 410
? 283 857
? 182 52
? 924 50
? 916 214
? 419 694
? 681 753
? 825 784
? 593 967
? 720 432
? 660 113
? 23...

result:


Subtask #3:

score: 0
Runtime Error

Test #88:

score: 0
Runtime Error

input:

1500
83
575
457
489
248
581
46
683
637
1027
705
1234
616
439
937
171
477
441
163
630
1117
58
770
304
700
124
1031
834
587
838
622
505
95
815
75
409
401
546
882
299
287
98
311
866
610
56
177
282
1411
25
267
643
273
343
645
52
486
162
176
398
123
251
1038
547
675
1037
592
553
319
718
217
93
663
232
20...

output:

? 1094 83
? 932 575
? 1120 457
? 934 489
? 755 248
? 1309 581
? 46 558
? 841 683
? 637 1113
? 1346 1027
? 705 1380
? 1234 1316
? 616 1258
? 548 439
? 937 1281
? 871 171
? 477 650
? 498 441
? 1095 163
? 630 1454
? 1117 1485
? 646 58
? 1330 770
? 900 304
? 700 793
? 1373 124
? 1031 1197
? 834 1194
? 5...

result: