oj.uz

Submission #836031

# Submission time Handle Problem Language Result Execution time Memory
836031 2023-08-24T05:35:55 Z Kerim Mechanical Doll (IOI18_doll) C++17
53 / 100
 99 ms 24880 KB 
#include "doll.h"
#include "bits/stdc++.h"
#define pb(x) push_back(x)
using namespace std;
const int N = 4e5+5;
vector<int> X, Y;
vector<int> adj[N];
int who[N], sw[N], S;
 
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 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;
    for (int i = 0; i < pw; i++)
        f(1, 0, pw/2, i);
    int root = get_switch();
    int to_the_root = pw - sz;
    for (int i = 1; i < pw / 2; i++){
        X.push_back(get_switch());
        Y.push_back(get_switch());
    }
    for (int i = 0; i < pw / 2; i++){
        int l = i * 2;
        int r = i * 2 + 1;
        if (who[l] < to_the_root) X.push_back(root);
        else X.push_back(values[who[l] - to_the_root]);
        if (who[r] < to_the_root) Y.push_back(root);
        else Y.push_back(values[who[r] - to_the_root]);
    }
    return root;
}
void create_circuit(int M, vector<int> A) {
    vector<int> C(M + 1);
    int N = A.size();
    if (N == 16 and 1 == 0){
        A.push_back(0);
        int one_root =  get_root(A);
        for (int i = 0; i <= M; ++i)
            C[i] = one_root;
    }
    else{
        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);
        for (int i = 0; i <= M; ++i)
            C[i] = get_root(adj[i]);
    }
    answer(C, X, Y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 24 ms 13396 KB Output is correct
3 Correct 19 ms 13136 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 12 ms 10836 KB Output is correct
6 Correct 28 ms 15436 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 5 ms 9684 KB Output is correct
2 Correct 24 ms 13396 KB Output is correct
3 Correct 19 ms 13136 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 12 ms 10836 KB Output is correct
6 Correct 28 ms 15436 KB Output is correct
7 Correct 4 ms 9684 KB Output is correct
8 Correct 36 ms 15952 KB Output is correct
9 Correct 40 ms 16584 KB Output is correct
10 Correct 55 ms 19520 KB Output is correct
11 Correct 5 ms 9684 KB Output is correct
12 Correct 5 ms 9684 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 5 ms 9684 KB Output is correct
2 Correct 24 ms 13396 KB Output is correct
3 Correct 19 ms 13136 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 12 ms 10836 KB Output is correct
6 Correct 28 ms 15436 KB Output is correct
7 Correct 4 ms 9684 KB Output is correct
8 Correct 36 ms 15952 KB Output is correct
9 Correct 40 ms 16584 KB Output is correct
10 Correct 55 ms 19520 KB Output is correct
11 Correct 5 ms 9684 KB Output is correct
12 Correct 5 ms 9684 KB Output is correct
13 Correct 5 ms 9684 KB Output is correct
14 Correct 69 ms 20868 KB Output is correct
15 Correct 37 ms 15404 KB Output is correct
16 Correct 54 ms 18512 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 61 ms 19900 KB Output is correct
21 Correct 6 ms 9684 KB Output is correct
22 Correct 6 ms 9684 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 9684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
9.0000000036 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 4 ms 9684 KB Output is partially correct
2 Correct 46 ms 15692 KB Output is correct
3 Partially correct 70 ms 19612 KB Output is partially correct
4 Partially correct 84 ms 20332 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 4 ms 9684 KB Output is partially correct
2 Correct 46 ms 15692 KB Output is correct
3 Partially correct 70 ms 19612 KB Output is partially correct
4 Partially correct 84 ms 20332 KB Output is partially correct
5 Partially correct 77 ms 21604 KB Output is partially correct
6 Partially correct 82 ms 22924 KB Output is partially correct
7 Partially correct 81 ms 22516 KB Output is partially correct
8 Partially correct 85 ms 23480 KB Output is partially correct
9 Partially correct 70 ms 19640 KB Output is partially correct
10 Partially correct 97 ms 24880 KB Output is partially correct
11 Partially correct 99 ms 24060 KB Output is partially correct
12 Partially correct 63 ms 19120 KB Output is partially correct
13 Partially correct 54 ms 18412 KB Output is partially correct
14 Partially correct 53 ms 18028 KB Output is partially correct
15 Partially correct 52 ms 17556 KB Output is partially correct
16 Partially correct 5 ms 9940 KB Output is partially correct
17 Partially correct 48 ms 16940 KB Output is partially correct
18 Partially correct 54 ms 16988 KB Output is partially correct
19 Partially correct 51 ms 17508 KB Output is partially correct
20 Partially correct 65 ms 19692 KB Output is partially correct
21 Partially correct 84 ms 21940 KB Output is partially correct
22 Partially correct 61 ms 18900 KB Output is partially correct