oj.uz

Submission #835620

# Submission time Handle Problem Language Result Execution time Memory
835620 2023-08-23T16:41:46 Z Kerim Mechanical Doll (IOI18_doll) C++17
69.553 / 100
 94 ms 21580 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) {
    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
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Incorrect 23 ms 13396 KB wrong serial number
3 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Incorrect 23 ms 13396 KB wrong serial number
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Incorrect 23 ms 13396 KB wrong serial number
3 Halted 0 ms 0 KB -

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 5 ms 9684 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 5 ms 9728 KB Output is correct
6 Correct 4 ms 9684 KB Output is correct
7 Correct 4 ms 9684 KB Output is correct
8 Correct 4 ms 9684 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9660 KB Output is correct
2 Correct 60 ms 17040 KB Output is correct
3 Correct 72 ms 19140 KB Output is correct
4 Correct 94 ms 21440 KB Output is correct

Subtask #6
41.5530038336 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9660 KB Output is correct
2 Correct 60 ms 17040 KB Output is correct
3 Correct 72 ms 19140 KB Output is correct
4 Correct 94 ms 21440 KB Output is correct
5 Partially correct 78 ms 21580 KB Output is partially correct
6 Partially correct 70 ms 21196 KB Output is partially correct
7 Partially correct 73 ms 21196 KB Output is partially correct
8 Partially correct 70 ms 20696 KB Output is partially correct
9 Partially correct 65 ms 17028 KB Output is partially correct
10 Partially correct 91 ms 20992 KB Output is partially correct
11 Partially correct 81 ms 19476 KB Output is partially correct
12 Partially correct 52 ms 16080 KB Output is partially correct
13 Partially correct 52 ms 17276 KB Output is partially correct
14 Partially correct 50 ms 17228 KB Output is partially correct
15 Partially correct 50 ms 17424 KB Output is partially correct
16 Partially correct 6 ms 9940 KB Output is partially correct
17 Partially correct 41 ms 15828 KB Output is partially correct
18 Partially correct 52 ms 15740 KB Output is partially correct
19 Partially correct 45 ms 15828 KB Output is partially correct
20 Partially correct 62 ms 19064 KB Output is partially correct
21 Partially correct 77 ms 19120 KB Output is partially correct
22 Partially correct 61 ms 18772 KB Output is partially correct