oj.uz

Submission #1040090

# Submission time Handle Problem Language Result Execution time Memory
1040090 2024-07-31T15:58:21 Z _8_8_ Magic Show (APIO24_show) C++17
100 / 100
 428 ms 132380 KB 
#include <bits/stdc++.h>
#include "Alice.h"
using namespace std;
typedef long long ll;
vector<pair<int,int>> vec;
const int N = 5e3;
int p[N + 12];
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int get(int v) {
    if(p[v] == v) return v;
    return p[v] = get(p[v]);
}
bool merge(int x,int y) {
    x = get(x);
    y = get(y);
    if(x == y) return false;
    p[x] = y;
    return 1;
}
vector<pair<int,int>> Alice(){
    long long x = setN(5000);
    iota(p+1,p+N+1,1);
    for(int i = 1;i <= N;i++) {
        for(int j = i+1; j <= N; j++) {
            ll t = (i + j) % 60;
            if((x >> t) & 1) {
                vec.push_back({i,j});
            }
        }
    }
    shuffle(vec.begin(),vec.end(),rng);
    vector<pair<int,int>> ans;
    for(auto [x,y]:vec) {
        if((int)ans.size() == 4999) break;
        if(merge(x,y)) {
            ans.push_back({x,y});
        }
    }
    return ans;
}

#include <vector>
#include "Bob.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
long long Bob(std::vector<std::pair<int,int>> V){
    ll X = 0;
    for(auto [x,y]:V) {
        X |= (1ll << ((x + y) % 60));
    }
    return X;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 18764 KB Correct.
2 Correct 43 ms 18252 KB Correct.
3 Correct 20 ms 9664 KB Correct.
4 Correct 28 ms 10588 KB Correct.
5 Correct 34 ms 17576 KB Correct.
6 Correct 48 ms 17740 KB Correct.
7 Correct 28 ms 9808 KB Correct.
8 Correct 29 ms 10832 KB Correct.
9 Correct 37 ms 17564 KB Correct.
10 Correct 35 ms 19096 KB Correct.
11 Correct 37 ms 18252 KB Correct.
12 Correct 21 ms 10264 KB Correct.

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 18764 KB Correct.
2 Correct 43 ms 18252 KB Correct.
3 Correct 20 ms 9664 KB Correct.
4 Correct 28 ms 10588 KB Correct.
5 Correct 34 ms 17576 KB Correct.
6 Correct 48 ms 17740 KB Correct.
7 Correct 28 ms 9808 KB Correct.
8 Correct 29 ms 10832 KB Correct.
9 Correct 37 ms 17564 KB Correct.
10 Correct 35 ms 19096 KB Correct.
11 Correct 37 ms 18252 KB Correct.
12 Correct 21 ms 10264 KB Correct.
13 Correct 59 ms 35644 KB Correct.
14 Correct 62 ms 35388 KB Correct.
15 Correct 64 ms 33864 KB Correct.
16 Correct 60 ms 35144 KB Correct.
17 Correct 66 ms 34616 KB Correct.
18 Correct 65 ms 34896 KB Correct.
19 Correct 69 ms 34376 KB Correct.
20 Correct 85 ms 35040 KB Correct.
21 Correct 47 ms 19020 KB Correct.
22 Correct 55 ms 34888 KB Correct.
23 Correct 44 ms 18328 KB Correct.
24 Correct 80 ms 33860 KB Correct.

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 18764 KB Correct.
2 Correct 43 ms 18252 KB Correct.
3 Correct 20 ms 9664 KB Correct.
4 Correct 28 ms 10588 KB Correct.
5 Correct 34 ms 17576 KB Correct.
6 Correct 48 ms 17740 KB Correct.
7 Correct 28 ms 9808 KB Correct.
8 Correct 29 ms 10832 KB Correct.
9 Correct 37 ms 17564 KB Correct.
10 Correct 35 ms 19096 KB Correct.
11 Correct 37 ms 18252 KB Correct.
12 Correct 21 ms 10264 KB Correct.
13 Correct 59 ms 35644 KB Correct.
14 Correct 62 ms 35388 KB Correct.
15 Correct 64 ms 33864 KB Correct.
16 Correct 60 ms 35144 KB Correct.
17 Correct 66 ms 34616 KB Correct.
18 Correct 65 ms 34896 KB Correct.
19 Correct 69 ms 34376 KB Correct.
20 Correct 85 ms 35040 KB Correct.
21 Correct 47 ms 19020 KB Correct.
22 Correct 55 ms 34888 KB Correct.
23 Correct 44 ms 18328 KB Correct.
24 Correct 80 ms 33860 KB Correct.
25 Correct 259 ms 66600 KB Correct.
26 Correct 178 ms 68064 KB Correct.
27 Correct 180 ms 68392 KB Correct.
28 Correct 250 ms 66660 KB Correct.
29 Correct 167 ms 68020 KB Correct.
30 Correct 190 ms 67616 KB Correct.
31 Correct 229 ms 66604 KB Correct.
32 Correct 246 ms 66600 KB Correct.
33 Correct 223 ms 68620 KB Correct.
34 Correct 174 ms 68108 KB Correct.
35 Correct 223 ms 66860 KB Correct.
36 Correct 181 ms 67368 KB Correct.
37 Correct 231 ms 67588 KB Correct.
38 Correct 257 ms 66628 KB Correct.
39 Correct 295 ms 67704 KB Correct.
40 Correct 428 ms 132380 KB Correct.
41 Correct 218 ms 67952 KB Correct.
42 Correct 192 ms 68160 KB Correct.
43 Correct 217 ms 67284 KB Correct.
44 Correct 134 ms 67692 KB Correct.