QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#765473#8267. Staring Contest_8_8_#0 3ms12740kbC++204.1kb2024-11-20 14:23:522024-11-20 14:23:52

Judging History

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

  • [2024-11-20 14:23:52]
  • 评测
  • 测评结果:0
  • 用时:3ms
  • 内存:12740kb
  • [2024-11-20 14:23:52]
  • 提交

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--;
    // shuffle(x.begin(), x.end(), rng);
    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(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: 3ms
memory: 12516kb

input:

2
1

output:

? 2 1
! 1 1 

result:

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

Test #2:

score: 9
Accepted
time: 3ms
memory: 12740kb

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

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

output:

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

result:


Subtask #2:

score: 0
Runtime Error

Test #58:

score: 0
Runtime Error

input:

1000
500
232
123
67
227
340
97
226
376
567
740
579
690
390
255
260
194
248
98
99
22
525
88
471
584
208
279
298
475
657
625
497
568
676
239
29
600
50
768
190
246
109
8
304
154
148
158
391
271
837
629
611
293
69
74
578
122
168
534
301
521
531
217
224
408
724
244
320
542
132
425
49
451
36
403
198
786
2...

output:

? 500 664
? 422 232
? 779 123
? 594 67
? 544 227
? 490 340
? 956 97
? 226 533
? 516 376
? 697 567
? 852 740
? 776 579
? 941 690
? 527 390
? 709 255
? 537 260
? 194 372
? 606 248
? 98 447
? 99 461
? 889 22
? 771 525
? 88 552
? 720 471
? 746 584
? 208 991
? 811 279
? 575 298
? 475 945
? 887 657
? 965 ...

result:


Subtask #3:

score: 0
Runtime Error

Test #88:

score: 0
Runtime Error

input:

1500
1
535
706
154
837
293
304
231
402
383
637
233
222
1107
460
10
568
628
695
165
554
619
162
73
886
89
115
388
305
46
548
90
18
690
969
609
84
83
294
1344
478
28
465
623
666
272
1022
537
63
791
606
423
134
1227
494
1051
43
428
442
686
269
499
104
768
885
1302
1445
775
232
493
597
61
194
374
69
588...

output:

? 1070 1
? 721 535
? 706 1254
? 1035 154
? 837 1397
? 293 1139
? 576 304
? 1058 231
? 402 1471
? 383 1363
? 637 1231
? 233 1458
? 222 332
? 1411 1107
? 667 460
? 10 1283
? 1125 568
? 801 628
? 695 1389
? 1387 165
? 554 1358
? 1406 619
? 1401 162
? 73 705
? 1483 886
? 1073 89
? 115 716
? 1034 388
? 3...

result: