oj.uz

Submission #138889

# Submission time Handle Problem Language Result Execution time Memory
138889 2019-07-30T18:58:37 Z evpipis Mechanical Doll (IOI18_doll) C++14
100 / 100
 186 ms 10768 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

const int len = 3e5+5;
int lef[len], rig[len], arr[len], vis[len], cnt, pos;

int build(int l, int r){
    if (l == r)
        return l;

    int mid = (l+r)/2, cur = ++cnt;
    lef[cur] = build(l, mid);
    rig[cur] = build(mid+1, r);

    //printf("build: l = %d, r = %d\n", l, r);
    //printf("switch = %d, lef = %d, rig = %d\n", -cur, lef[cur], rig[cur]);
    return -cur;
}

int fix(int num, int lim, int j){
    int cur = ++cnt;
    if (num&(1<<j))
        lef[cur] = build(lim+1, lim+(1<<j)), num -= (1<<j), lim += (1<<j);
    else
        lef[cur] = -1;

    if (j == 0)
        rig[cur] = 0;
    else
        rig[cur] = fix(num, lim, j-1);

    //printf("fix: j = %d\n", j);
    //printf("cur = %d, lef = %d, rig = %d\n", -cur, lef[cur], rig[cur]);
    return -cur;
}

void create_circuit(int m, vector<int> A) {
    int n = A.size();
    for (int i = 1; i <= n; i++)
        arr[i] = A[i-1];

    int j = 0;
    while ((1<<j) <= n)
        j++;

    vector<int> C(m+1);
    C[0] = fix(n, 0, j-1);
    for (int i = 1; i <= m; i++)
        C[i] = C[0];

    //printf("c0 = %d\n", C[0]);

    int cur = -1;
    while (cur != 0){
        //printf("cur = %d\n", cur);
        if (!vis[-cur]){
            vis[-cur] ^= 1;
            if (lef[-cur] >= 1)
                lef[-cur] = arr[++pos], cur = C[0];
            else
                cur = lef[-cur];
        }
        else{
            vis[-cur] ^= 1;
            if (rig[-cur] >= 1)
                rig[-cur] = arr[++pos], cur = C[0];
            else
                cur = rig[-cur];
        }
    }

    vector<int> X(cnt), Y(cnt);
    for (int i = 0; i < cnt; i++)
        X[i] = lef[i+1], Y[i] = rig[i+1];

    answer(C, X, Y);
}
/*
4 4
1 2 1 3
*/

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 62 ms 4548 KB Output is correct
3 Correct 52 ms 4212 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1484 KB Output is correct
6 Correct 102 ms 6116 KB Output is correct
7 Correct 2 ms 224 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 62 ms 4548 KB Output is correct
3 Correct 52 ms 4212 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1484 KB Output is correct
6 Correct 102 ms 6116 KB Output is correct
7 Correct 2 ms 224 KB Output is correct
8 Correct 113 ms 7236 KB Output is correct
9 Correct 102 ms 7620 KB Output is correct
10 Correct 186 ms 10768 KB Output is correct
11 Correct 2 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 2 ms 256 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 62 ms 4548 KB Output is correct
3 Correct 52 ms 4212 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1484 KB Output is correct
6 Correct 102 ms 6116 KB Output is correct
7 Correct 2 ms 224 KB Output is correct
8 Correct 113 ms 7236 KB Output is correct
9 Correct 102 ms 7620 KB Output is correct
10 Correct 186 ms 10768 KB Output is correct
11 Correct 2 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 183 ms 10516 KB Output is correct
15 Correct 116 ms 6828 KB Output is correct
16 Correct 171 ms 10188 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 2 ms 204 KB Output is correct
20 Correct 136 ms 10564 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 2 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 224 KB Output is correct
2 Correct 2 ms 244 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 2 ms 256 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 224 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 2 ms 224 KB Output is correct
2 Correct 85 ms 6456 KB Output is correct
3 Correct 78 ms 6464 KB Output is correct
4 Correct 135 ms 9608 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 224 KB Output is correct
2 Correct 85 ms 6456 KB Output is correct
3 Correct 78 ms 6464 KB Output is correct
4 Correct 135 ms 9608 KB Output is correct
5 Correct 129 ms 10148 KB Output is correct
6 Correct 154 ms 9904 KB Output is correct
7 Correct 171 ms 10036 KB Output is correct
8 Correct 140 ms 9796 KB Output is correct
9 Correct 91 ms 6468 KB Output is correct
10 Correct 140 ms 9764 KB Output is correct
11 Correct 141 ms 9620 KB Output is correct
12 Correct 86 ms 6460 KB Output is correct
13 Correct 97 ms 6652 KB Output is correct
14 Correct 96 ms 6700 KB Output is correct
15 Correct 99 ms 6796 KB Output is correct
16 Correct 5 ms 460 KB Output is correct
17 Correct 84 ms 6440 KB Output is correct
18 Correct 98 ms 6432 KB Output is correct
19 Correct 101 ms 6460 KB Output is correct
20 Correct 148 ms 9648 KB Output is correct
21 Correct 157 ms 9612 KB Output is correct
22 Correct 159 ms 9636 KB Output is correct