oj.uz

Submission #1040087

# Submission time Handle Problem Language Result Execution time Memory
1040087 2024-07-31T15:57:05 Z _8_8_ Magic Show (APIO24_show) C++17
35 / 100
 1000 ms 262984 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 = 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 89 ms 35124 KB Correct.
2 Correct 90 ms 35132 KB Correct.
3 Correct 45 ms 17568 KB Correct.
4 Correct 60 ms 18252 KB Correct.
5 Correct 70 ms 33856 KB Correct.
6 Correct 96 ms 34880 KB Correct.
7 Correct 51 ms 17996 KB Correct.
8 Correct 63 ms 19108 KB Correct.
9 Correct 84 ms 35464 KB Correct.
10 Correct 69 ms 34880 KB Correct.
11 Correct 70 ms 34368 KB Correct.
12 Correct 45 ms 17740 KB Correct.

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 35124 KB Correct.
2 Correct 90 ms 35132 KB Correct.
3 Correct 45 ms 17568 KB Correct.
4 Correct 60 ms 18252 KB Correct.
5 Correct 70 ms 33856 KB Correct.
6 Correct 96 ms 34880 KB Correct.
7 Correct 51 ms 17996 KB Correct.
8 Correct 63 ms 19108 KB Correct.
9 Correct 84 ms 35464 KB Correct.
10 Correct 69 ms 34880 KB Correct.
11 Correct 70 ms 34368 KB Correct.
12 Correct 45 ms 17740 KB Correct.
13 Correct 190 ms 68396 KB Correct.
14 Correct 190 ms 68292 KB Correct.
15 Correct 203 ms 67368 KB Correct.
16 Correct 160 ms 67112 KB Correct.
17 Correct 184 ms 67752 KB Correct.
18 Correct 232 ms 68136 KB Correct.
19 Correct 180 ms 67628 KB Correct.
20 Correct 255 ms 66860 KB Correct.
21 Correct 91 ms 35400 KB Correct.
22 Correct 147 ms 67388 KB Correct.
23 Correct 97 ms 35644 KB Correct.
24 Correct 226 ms 67888 KB Correct.

Subtask #3
0.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 35124 KB Correct.
2 Correct 90 ms 35132 KB Correct.
3 Correct 45 ms 17568 KB Correct.
4 Correct 60 ms 18252 KB Correct.
5 Correct 70 ms 33856 KB Correct.
6 Correct 96 ms 34880 KB Correct.
7 Correct 51 ms 17996 KB Correct.
8 Correct 63 ms 19108 KB Correct.
9 Correct 84 ms 35464 KB Correct.
10 Correct 69 ms 34880 KB Correct.
11 Correct 70 ms 34368 KB Correct.
12 Correct 45 ms 17740 KB Correct.
13 Correct 190 ms 68396 KB Correct.
14 Correct 190 ms 68292 KB Correct.
15 Correct 203 ms 67368 KB Correct.
16 Correct 160 ms 67112 KB Correct.
17 Correct 184 ms 67752 KB Correct.
18 Correct 232 ms 68136 KB Correct.
19 Correct 180 ms 67628 KB Correct.
20 Correct 255 ms 66860 KB Correct.
21 Correct 91 ms 35400 KB Correct.
22 Correct 147 ms 67388 KB Correct.
23 Correct 97 ms 35644 KB Correct.
24 Correct 226 ms 67888 KB Correct.
25 Correct 649 ms 132952 KB Correct.
26 Correct 493 ms 132128 KB Correct.
27 Correct 532 ms 132080 KB Correct.
28 Correct 666 ms 132120 KB Correct.
29 Correct 492 ms 132456 KB Correct.
30 Correct 559 ms 132120 KB Correct.
31 Correct 653 ms 132104 KB Correct.
32 Correct 686 ms 132116 KB Correct.
33 Correct 610 ms 132120 KB Correct.
34 Correct 502 ms 132144 KB Correct.
35 Correct 602 ms 134024 KB Correct.
36 Correct 529 ms 132692 KB Correct.
37 Correct 688 ms 132132 KB Correct.
38 Correct 720 ms 132520 KB Correct.
39 Correct 882 ms 132268 KB Correct.
40 Execution timed out 1065 ms 262984 KB Time limit exceeded
41 Halted 0 ms 0 KB -