QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#765493#8267. Staring Contest_8_8_#0 3ms12776kbC++204.1kb2024-11-20 14:26:272024-11-20 14:26:33

Judging History

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

  • [2024-11-20 14:26:33]
  • 评测
  • 测评结果:0
  • 用时:3ms
  • 内存:12776kb
  • [2024-11-20 14:26:27]
  • 提交

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(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: 12776kb

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: 3ms
memory: 12528kb

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

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

output:

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

result:


Subtask #2:

score: 0
Runtime Error

Test #58:

score: 0
Runtime Error

input:

1000
274
73
331
419
124
391
92
8
759
176
687
347
104
119
123
295
584
86
502
405
700
213
384
250
29
933
139
767
19
444
513
671
282
230
363
196
219
820
459
627
383
330
202
431
120
107
189
111
456
623
650
39
234
300
14
106
553
74
606
496
536
1
77
469
400
927
2
897
3
351
516
173
241
277
576
180
198
957
...

output:

? 995 274
? 315 73
? 482 331
? 419 550
? 124 369
? 979 391
? 92 914
? 438 8
? 759 803
? 757 176
? 687 898
? 971 347
? 104 186
? 555 119
? 123 338
? 295 596
? 816 584
? 86 158
? 502 714
? 863 405
? 700 751
? 213 561
? 890 384
? 903 250
? 97 29
? 956 933
? 212 139
? 767 860
? 604 19
? 965 444
? 513 77...

result:


Subtask #3:

score: 0
Runtime Error

Test #88:

score: 0
Runtime Error

input:

1500
120
452
1359
633
490
534
194
596
450
709
663
104
715
503
80
545
299
550
184
711
45
76
381
1224
264
478
509
531
618
175
753
664
26
268
786
823
479
144
394
339
386
987
226
842
1089
197
861
400
285
981
1017
372
169
309
291
695
641
441
256
1039
293
319
951
397
1055
759
220
72
246
434
162
156
267
56...

output:

? 120 313
? 517 452
? 1386 1359
? 633 1167
? 490 500
? 877 534
? 194 661
? 673 596
? 450 1106
? 1175 709
? 663 1214
? 104 123
? 1475 715
? 503 1259
? 80 236
? 836 545
? 299 890
? 550 794
? 184 1369
? 1052 711
? 45 1293
? 1290 76
? 381 1097
? 1439 1224
? 756 264
? 662 478
? 509 852
? 531 1105
? 1257 ...

result: