oj.uz

Submission #835625

# Submission time Handle Problem Language Result Execution time Memory
835625 2023-08-23T16:44:19 Z Kerim Mechanical Doll (IOI18_doll) C++17
100 / 100
 113 ms 23944 KB 
#include "doll.h"
#include "bits/stdc++.h"
#define pb(x) push_back(x)
using namespace std;
const int N = 4e5+5;
vector<int> adj[N], id;
int who[N], sw[N], S, XX[N], YY[N];

void f(int nd, int pos, int pw, int id){
    if (!pw){
        who[pos] = id;
        return;
    }
    sw[nd] ^= 1;
    if (sw[nd])
        f(nd*2, pos, pw/2, id);
    else
        f(nd*2+1, pos+pw, pw/2, id);
}
int get_switch(){
    return --S;
}
int dfs(int l, int r, int rem, int root, vector<int>&values){
    if (r < rem)
        return root;
    if (l == r)
        return values[who[l]];
    int nd = get_switch();
    int mid = (l+r) >> 1;
    XX[-nd] = dfs(l, mid, rem, root, values);
    YY[-nd] = dfs(mid+1, r, rem, root, values);
    return nd;
}
int get_root(vector<int> &values){
    int sz = values.size();
    int pw = 1;
    while (pw < sz) pw *= 2;
    id.clear();
    for (int i = 0; i < pw; i++)
        f(1, 0, pw/2, i), id.pb(i);
    for (int i = 0; i < pw-sz; i++)
        who[i] = pw;
    sort(id.begin(), id.end(), [&](int x, int y){
        return (who[x] < who[y]);
    });
    for (int i = 0; i < sz; i++)
        who[id[i]] = i;
    return dfs(0, pw-1, pw-sz, S-1, values);
}
void create_circuit(int M, vector<int> A) {
    A.pb(0);
    int entire_root = get_root(A);
    vector<int> C(M + 1);
    for (int i = 0; i <= M; ++i)
        C[i] = entire_root;
    vector<int> X(-S), Y(-S);
    for (int i = 1; i <= -S; i++)
        X[i-1] = XX[i], Y[i-1] = YY[i];
    answer(C, X, Y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 44 ms 15000 KB Output is correct
3 Correct 39 ms 15296 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 12 ms 10836 KB Output is correct
6 Correct 53 ms 17468 KB Output is correct
7 Correct 4 ms 9684 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 44 ms 15000 KB Output is correct
3 Correct 39 ms 15296 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 12 ms 10836 KB Output is correct
6 Correct 53 ms 17468 KB Output is correct
7 Correct 4 ms 9684 KB Output is correct
8 Correct 84 ms 20024 KB Output is correct
9 Correct 74 ms 20552 KB Output is correct
10 Correct 106 ms 23944 KB Output is correct
11 Correct 4 ms 9684 KB Output is correct
12 Correct 4 ms 9684 KB Output is correct
13 Correct 4 ms 9684 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 44 ms 15000 KB Output is correct
3 Correct 39 ms 15296 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 12 ms 10836 KB Output is correct
6 Correct 53 ms 17468 KB Output is correct
7 Correct 4 ms 9684 KB Output is correct
8 Correct 84 ms 20024 KB Output is correct
9 Correct 74 ms 20552 KB Output is correct
10 Correct 106 ms 23944 KB Output is correct
11 Correct 4 ms 9684 KB Output is correct
12 Correct 4 ms 9684 KB Output is correct
13 Correct 4 ms 9684 KB Output is correct
14 Correct 96 ms 23456 KB Output is correct
15 Correct 71 ms 19572 KB Output is correct
16 Correct 109 ms 23172 KB Output is correct
17 Correct 4 ms 9684 KB Output is correct
18 Correct 6 ms 9732 KB Output is correct
19 Correct 5 ms 9684 KB Output is correct
20 Correct 101 ms 23588 KB Output is correct
21 Correct 4 ms 9684 KB Output is correct
22 Correct 4 ms 9684 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 4 ms 9684 KB Output is correct
3 Correct 4 ms 9672 KB Output is correct
4 Correct 5 ms 9672 KB Output is correct
5 Correct 4 ms 9684 KB Output is correct
6 Correct 6 ms 9684 KB Output is correct
7 Correct 4 ms 9684 KB Output is correct
8 Correct 5 ms 9712 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 70 ms 18628 KB Output is correct
3 Correct 68 ms 18560 KB Output is correct
4 Correct 101 ms 21636 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 70 ms 18628 KB Output is correct
3 Correct 68 ms 18560 KB Output is correct
4 Correct 101 ms 21636 KB Output is correct
5 Correct 97 ms 23000 KB Output is correct
6 Correct 94 ms 22664 KB Output is correct
7 Correct 113 ms 22836 KB Output is correct
8 Correct 98 ms 22412 KB Output is correct
9 Correct 68 ms 18624 KB Output is correct
10 Correct 107 ms 22356 KB Output is correct
11 Correct 104 ms 22032 KB Output is correct
12 Correct 69 ms 18752 KB Output is correct
13 Correct 70 ms 19196 KB Output is correct
14 Correct 70 ms 19312 KB Output is correct
15 Correct 95 ms 19452 KB Output is correct
16 Correct 6 ms 9940 KB Output is correct
17 Correct 61 ms 17768 KB Output is correct
18 Correct 72 ms 18716 KB Output is correct
19 Correct 71 ms 18816 KB Output is correct
20 Correct 96 ms 22372 KB Output is correct
21 Correct 93 ms 22064 KB Output is correct
22 Correct 95 ms 22056 KB Output is correct