oj.uz

Submission #314215

# Submission time Handle Problem Language Result Execution time Memory
314215 2020-10-19T05:53:28 Z jainbot27 Mechanical Doll (IOI18_doll) C++17
100 / 100
 570 ms 36768 KB 
#include <bits/stdc++.h>
#include "doll.h"
using namespace std;

#define f first
#define s second
#define pb push_back
#define ar array
#define all(x) x.begin(), x.end()
#define siz(x) (int)x.size()

#define FOR(x, y, z) for(int x = (y); x < (z); x++)
#define ROF(x, z, y) for(int x = (y-1); x >= (z); x--)
#define F0R(x, z) FOR(x, 0, z)
#define R0F(x, z) ROF(x, 0, z)
#define trav(x, y) for(auto&x:y)

using ll = long long;
using vi = vector<int>;
using vl = vector<long long>;
using pii = pair<int, int>;
using vpii = vector<pair<int, int>>;

template<class T> inline bool ckmin(T&a, T b) {return b < a ? a = b, 1 : 0;}
template<class T> inline bool ckmax(T&a, T b) {return b > a ? a = b, 1 : 0;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const char nl = '\n';
const int mxN = 1e6 + 10;
const int MOD = 1e9 + 7;
const long long infLL = 1e18;
int switches, m, n, p2 = 1, val = 1; vi x(mxN), y(mxN), c, a, arr;

vi label(int node){
    if(node >= p2) return vi{node - p2};
    vi l = label(node*2);
    vi r = label(node*2 + 1);
    vi res;
    F0R(i, siz(l)){
        res.pb(l[i]);
        res.pb(r[i]);
    }
    return res;
}
int cnt = 0;
int dfs(int u, int l, int r){
    if(r < p2 - n){
        return -1;
    }   
    if(l == r){
        return a[arr[l]];
    }
    int xyz = u;
    int m = (l + r)/2;
    cnt++;
    x[xyz] = dfs(cnt, l, m);
    y[xyz] = dfs(cnt, m+1, r);
    return -u-1;
}
void create_circuit(int M, vi A){
    a = A, m = M; n = siz(a);
    F0R(i, m+1){
        c.pb(-1);
    }
    while(p2 <= n){
        p2*=2;
    }
    n++;
    arr = label(1);
    set<int> com;
    map<int, int> mp;
    FOR(i, p2 - n, p2){
        com.insert(arr[i]);
    }
    int ctr = 0;
    trav(v, com){
        mp[v] = ctr++;
    }
    FOR(i, p2-n, p2){
        arr[i] = mp[arr[i]];
    }
    a.pb(0);
    dfs(0, 0, p2-1);
    x.resize(cnt); 
    y.resize(cnt);
    answer(c, x, y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8012 KB Output is correct
2 Correct 137 ms 18196 KB Output is correct
3 Correct 110 ms 18132 KB Output is correct
4 Correct 5 ms 8140 KB Output is correct
5 Correct 16 ms 9412 KB Output is correct
6 Correct 174 ms 23040 KB Output is correct
7 Correct 5 ms 8036 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8012 KB Output is correct
2 Correct 137 ms 18196 KB Output is correct
3 Correct 110 ms 18132 KB Output is correct
4 Correct 5 ms 8140 KB Output is correct
5 Correct 16 ms 9412 KB Output is correct
6 Correct 174 ms 23040 KB Output is correct
7 Correct 5 ms 8036 KB Output is correct
8 Correct 232 ms 27156 KB Output is correct
9 Correct 332 ms 27656 KB Output is correct
10 Correct 397 ms 36768 KB Output is correct
11 Correct 7 ms 8140 KB Output is correct
12 Correct 6 ms 8012 KB Output is correct
13 Correct 6 ms 8012 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8012 KB Output is correct
2 Correct 137 ms 18196 KB Output is correct
3 Correct 110 ms 18132 KB Output is correct
4 Correct 5 ms 8140 KB Output is correct
5 Correct 16 ms 9412 KB Output is correct
6 Correct 174 ms 23040 KB Output is correct
7 Correct 5 ms 8036 KB Output is correct
8 Correct 232 ms 27156 KB Output is correct
9 Correct 332 ms 27656 KB Output is correct
10 Correct 397 ms 36768 KB Output is correct
11 Correct 7 ms 8140 KB Output is correct
12 Correct 6 ms 8012 KB Output is correct
13 Correct 6 ms 8012 KB Output is correct
14 Correct 531 ms 36252 KB Output is correct
15 Correct 268 ms 26704 KB Output is correct
16 Correct 411 ms 35988 KB Output is correct
17 Correct 8 ms 8140 KB Output is correct
18 Correct 6 ms 8140 KB Output is correct
19 Correct 6 ms 8012 KB Output is correct
20 Correct 486 ms 36464 KB Output is correct
21 Correct 5 ms 8140 KB Output is correct
22 Correct 5 ms 8012 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8140 KB Output is correct
2 Correct 6 ms 8144 KB Output is correct
3 Correct 7 ms 8140 KB Output is correct
4 Correct 6 ms 8012 KB Output is correct
5 Correct 5 ms 8012 KB Output is correct
6 Correct 8 ms 8140 KB Output is correct
7 Correct 5 ms 8140 KB Output is correct
8 Correct 6 ms 8136 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8012 KB Output is correct
2 Correct 415 ms 25684 KB Output is correct
3 Correct 271 ms 25696 KB Output is correct
4 Correct 398 ms 34456 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8012 KB Output is correct
2 Correct 415 ms 25684 KB Output is correct
3 Correct 271 ms 25696 KB Output is correct
4 Correct 398 ms 34456 KB Output is correct
5 Correct 400 ms 35812 KB Output is correct
6 Correct 413 ms 35512 KB Output is correct
7 Correct 502 ms 35628 KB Output is correct
8 Correct 428 ms 35228 KB Output is correct
9 Correct 265 ms 25760 KB Output is correct
10 Correct 462 ms 35196 KB Output is correct
11 Correct 570 ms 34796 KB Output is correct
12 Correct 251 ms 26020 KB Output is correct
13 Correct 292 ms 26284 KB Output is correct
14 Correct 278 ms 26428 KB Output is correct
15 Correct 306 ms 26564 KB Output is correct
16 Correct 11 ms 8652 KB Output is correct
17 Correct 210 ms 25732 KB Output is correct
18 Correct 243 ms 26252 KB Output is correct
19 Correct 308 ms 26260 KB Output is correct
20 Correct 506 ms 35504 KB Output is correct
21 Correct 453 ms 35244 KB Output is correct
22 Correct 418 ms 35264 KB Output is correct