oj.uz

Submission #835617

# Submission time Handle Problem Language Result Execution time Memory
835617 2023-08-23T16:40:44 Z Kerim Mechanical Doll (IOI18_doll) C++17
85.553 / 100
 92 ms 21496 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();
    if (sz == 0)
        return 0;
    if (sz == 1)
        return values[0];
    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) {
    int N = A.size();
    adj[0].pb(A[0]);
    for (int i = 0; i < N - 1; i++)
        adj[A[i]].pb(A[i+1]);
    adj[A[N-1]].pb(0);
    vector<int> C(M + 1);
    for (int i = 0; i <= M; ++i)
        C[i] = get_root(adj[i]);
    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 22 ms 13396 KB Output is correct
3 Correct 20 ms 13012 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 12 ms 10848 KB Output is correct
6 Correct 43 ms 14808 KB Output is correct
7 Correct 5 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 22 ms 13396 KB Output is correct
3 Correct 20 ms 13012 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 12 ms 10848 KB Output is correct
6 Correct 43 ms 14808 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 38 ms 15572 KB Output is correct
9 Correct 46 ms 15944 KB Output is correct
10 Correct 59 ms 18688 KB Output is correct
11 Correct 6 ms 9612 KB Output is correct
12 Correct 5 ms 9700 KB Output is correct
13 Correct 5 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 22 ms 13396 KB Output is correct
3 Correct 20 ms 13012 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 12 ms 10848 KB Output is correct
6 Correct 43 ms 14808 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 38 ms 15572 KB Output is correct
9 Correct 46 ms 15944 KB Output is correct
10 Correct 59 ms 18688 KB Output is correct
11 Correct 6 ms 9612 KB Output is correct
12 Correct 5 ms 9700 KB Output is correct
13 Correct 5 ms 9684 KB Output is correct
14 Correct 69 ms 20340 KB Output is correct
15 Correct 39 ms 15188 KB Output is correct
16 Correct 59 ms 18108 KB Output is correct
17 Correct 5 ms 9684 KB Output is correct
18 Correct 4 ms 9684 KB Output is correct
19 Correct 4 ms 9684 KB Output is correct
20 Correct 63 ms 19324 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 5 ms 9684 KB Output is correct
2 Correct 5 ms 9720 KB Output is correct
3 Correct 6 ms 9708 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9692 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 4 ms 9684 KB Output is correct
8 Correct 4 ms 9704 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 56 ms 17020 KB Output is correct
3 Correct 68 ms 19072 KB Output is correct
4 Correct 92 ms 21488 KB Output is correct

Subtask #6
41.5530038336 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 56 ms 17020 KB Output is correct
3 Correct 68 ms 19072 KB Output is correct
4 Correct 92 ms 21488 KB Output is correct
5 Partially correct 74 ms 21496 KB Output is partially correct
6 Partially correct 71 ms 21248 KB Output is partially correct
7 Partially correct 73 ms 21248 KB Output is partially correct
8 Partially correct 67 ms 20600 KB Output is partially correct
9 Partially correct 63 ms 17004 KB Output is partially correct
10 Partially correct 87 ms 20952 KB Output is partially correct
11 Partially correct 85 ms 19432 KB Output is partially correct
12 Partially correct 52 ms 16180 KB Output is partially correct
13 Partially correct 47 ms 17260 KB Output is partially correct
14 Partially correct 49 ms 17268 KB Output is partially correct
15 Partially correct 50 ms 17492 KB Output is partially correct
16 Partially correct 6 ms 9940 KB Output is partially correct
17 Partially correct 42 ms 15864 KB Output is partially correct
18 Partially correct 53 ms 15744 KB Output is partially correct
19 Partially correct 44 ms 15860 KB Output is partially correct
20 Partially correct 67 ms 18976 KB Output is partially correct
21 Partially correct 83 ms 19024 KB Output is partially correct
22 Partially correct 61 ms 18772 KB Output is partially correct