oj.uz

Submission #83254

# Submission time Handle Problem Language Result Execution time Memory
83254 2018-11-06T12:18:04 Z win11905 Mechanical Doll (IOI18_doll) C++14
100 / 100
 124 ms 12024 KB 
#include "doll.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define x first
#define y second
using namespace std;

const int N = 3e5+5;

vector<int> A, X, Y;
int M, ptr = 1;
pii g[N];
bool state[N];

void solve(int p, int l, int r) {
    int m = (l + r) >> 1;
    if(l + 1 == r) {
        if(M <= m) g[p].x = 1;
        return;
    }
    g[p].y = ++ptr;
    solve(ptr, l, m);
    if(M > m) {
        g[p].x = ++ptr;
        solve(ptr, m+1, r);
    } else {
        g[p].x = 1;
    }
}

void dfs(int p, int v) {
    state[p] ^= 1;
    if(!state[p]) {
        if(g[p].y) dfs(g[p].y, v);
        else g[p].y = v;
    } else {
        if(g[p].x) dfs(g[p].x, v);
        else g[p].x = v;
    }
}

void create_circuit(int M, vector<int> A) {
    vector<int> C;
    C.emplace_back(A[0]);
    for(int i = 1; i <= M; ++i) C.emplace_back(-1);
    ::A = A;
    ::M = A.size();
    A.emplace_back(0);
    int z = 1;
    while(z * 2 <= ::M-1) z *= 2;
    z *= 2;
    solve(1, 1, z);
    for(int i = 1; i <= ::M; ++i) dfs(1, -A[i]);
    for(int i = 1; i <= ptr; ++i) X.emplace_back(-g[i].x), Y.emplace_back(-g[i].y);
    answer(C, X, Y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 60 ms 4496 KB Output is correct
3 Correct 42 ms 4708 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 14 ms 1604 KB Output is correct
6 Correct 65 ms 6772 KB Output is correct
7 Correct 1 ms 204 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 60 ms 4496 KB Output is correct
3 Correct 42 ms 4708 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 14 ms 1604 KB Output is correct
6 Correct 65 ms 6772 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 81 ms 8000 KB Output is correct
9 Correct 88 ms 8408 KB Output is correct
10 Correct 122 ms 12024 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 60 ms 4496 KB Output is correct
3 Correct 42 ms 4708 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 14 ms 1604 KB Output is correct
6 Correct 65 ms 6772 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 81 ms 8000 KB Output is correct
9 Correct 88 ms 8408 KB Output is correct
10 Correct 122 ms 12024 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 116 ms 11664 KB Output is correct
15 Correct 80 ms 7504 KB Output is correct
16 Correct 115 ms 11508 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 121 ms 11824 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 71 ms 7092 KB Output is correct
3 Correct 68 ms 6756 KB Output is correct
4 Correct 115 ms 10156 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 71 ms 7092 KB Output is correct
3 Correct 68 ms 6756 KB Output is correct
4 Correct 115 ms 10156 KB Output is correct
5 Correct 121 ms 11368 KB Output is correct
6 Correct 115 ms 11072 KB Output is correct
7 Correct 119 ms 11180 KB Output is correct
8 Correct 111 ms 11164 KB Output is correct
9 Correct 69 ms 6756 KB Output is correct
10 Correct 113 ms 10912 KB Output is correct
11 Correct 109 ms 10532 KB Output is correct
12 Correct 81 ms 6992 KB Output is correct
13 Correct 74 ms 7400 KB Output is correct
14 Correct 82 ms 7436 KB Output is correct
15 Correct 73 ms 7436 KB Output is correct
16 Correct 3 ms 460 KB Output is correct
17 Correct 89 ms 7360 KB Output is correct
18 Correct 71 ms 7268 KB Output is correct
19 Correct 73 ms 7016 KB Output is correct
20 Correct 114 ms 11064 KB Output is correct
21 Correct 124 ms 10524 KB Output is correct
22 Correct 109 ms 10524 KB Output is correct