oj.uz

Submission #292724

# Submission time Handle Problem Language Result Execution time Memory
292724 2020-09-07T12:23:30 Z Hideo Mechanical Doll (IOI18_doll) C++17
100 / 100
 136 ms 15648 KB 
#include "doll.h"
//#include "grader.cpp"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define fr first
#define sc second
#define pi pair < int, int >
#define vi vector < int >
#define pb push_back

const int MAXN = 4e5 + 7;
const int con = 3e7 + 7;

vi a, C, X, Y;
int n, sz, t, c;

struct sw{
    int x, y, nxt;
    sw(){
        x = y = nxt = 0;
    }
} s[MAXN];

void build (int v, int l, int r){
    if (l + 1 == r){
        if (sz - l + 1 > n)
            s[v].x = 1;
        return;
    }
    int mid = (l + r) >> 1;
    if (sz - mid + 1 <= n){
        s[v].x = ++t;
        build(t, l, mid);
    }
    else
        s[v].x = 1;
    s[v].y = ++t;
    build(t, mid + 1, r);
}

void reshuffle (int v){
    if (!s[v].nxt){
        s[v].nxt = 1;
        if (s[v].x)
            reshuffle(s[v].x);
        else {
            s[v].x = con + a[++c];
            if (a[c] == 0)
                assert(false);
            reshuffle(1);
        }
    }
    else {
        s[v].nxt = 0;
        if (s[v].y)
            reshuffle(s[v].y);
        else {
            s[v].y = con + a[++c];
            if (a[c] == 0)
                return;
            reshuffle(1);
        }
    }
}

void create_circuit(int M, vector <int> A) {
    a = A;
    n = a.size();
    if (n == 1){
        C.pb(a[0]);
        C.pb(0);
        answer(C, X, Y);
        return;
    }
    t = 1;
    a.pb(0);
    sz = (1 << int(ceil(log2(n))));
    build(1, 1, sz);
    reshuffle(1);
    for (int i = 1; i <= t; i++){
        if (s[i].x < con)
            X.pb(-s[i].x);
        else
            X.pb(s[i].x - con);
        if (s[i].y < con)
            Y.pb(-s[i].y);
        else
            Y.pb(s[i].y - con);
    }
    C.pb(a[0]);
    for (int i = 1; i <= M; i++)
        C.pb(-1);
    answer(C, X, Y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 48 ms 9008 KB Output is correct
3 Correct 47 ms 9104 KB Output is correct
4 Correct 4 ms 4960 KB Output is correct
5 Correct 19 ms 6264 KB Output is correct
6 Correct 77 ms 10980 KB Output is correct
7 Correct 5 ms 4940 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 48 ms 9008 KB Output is correct
3 Correct 47 ms 9104 KB Output is correct
4 Correct 4 ms 4960 KB Output is correct
5 Correct 19 ms 6264 KB Output is correct
6 Correct 77 ms 10980 KB Output is correct
7 Correct 5 ms 4940 KB Output is correct
8 Correct 83 ms 11836 KB Output is correct
9 Correct 86 ms 12344 KB Output is correct
10 Correct 124 ms 15648 KB Output is correct
11 Correct 4 ms 4940 KB Output is correct
12 Correct 5 ms 4940 KB Output is correct
13 Correct 5 ms 4940 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 48 ms 9008 KB Output is correct
3 Correct 47 ms 9104 KB Output is correct
4 Correct 4 ms 4960 KB Output is correct
5 Correct 19 ms 6264 KB Output is correct
6 Correct 77 ms 10980 KB Output is correct
7 Correct 5 ms 4940 KB Output is correct
8 Correct 83 ms 11836 KB Output is correct
9 Correct 86 ms 12344 KB Output is correct
10 Correct 124 ms 15648 KB Output is correct
11 Correct 4 ms 4940 KB Output is correct
12 Correct 5 ms 4940 KB Output is correct
13 Correct 5 ms 4940 KB Output is correct
14 Correct 128 ms 15388 KB Output is correct
15 Correct 78 ms 11364 KB Output is correct
16 Correct 136 ms 14748 KB Output is correct
17 Correct 4 ms 4940 KB Output is correct
18 Correct 4 ms 4940 KB Output is correct
19 Correct 5 ms 4940 KB Output is correct
20 Correct 131 ms 15472 KB Output is correct
21 Correct 4 ms 4940 KB Output is correct
22 Correct 5 ms 4940 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 74 ms 10620 KB Output is correct
3 Correct 79 ms 10284 KB Output is correct
4 Correct 114 ms 13084 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 74 ms 10620 KB Output is correct
3 Correct 79 ms 10284 KB Output is correct
4 Correct 114 ms 13084 KB Output is correct
5 Correct 134 ms 14696 KB Output is correct
6 Correct 120 ms 14244 KB Output is correct
7 Correct 118 ms 14316 KB Output is correct
8 Correct 115 ms 13888 KB Output is correct
9 Correct 86 ms 10280 KB Output is correct
10 Correct 116 ms 13904 KB Output is correct
11 Correct 116 ms 13480 KB Output is correct
12 Correct 76 ms 10532 KB Output is correct
13 Correct 85 ms 11012 KB Output is correct
14 Correct 110 ms 10980 KB Output is correct
15 Correct 84 ms 11132 KB Output is correct
16 Correct 6 ms 5196 KB Output is correct
17 Correct 81 ms 10776 KB Output is correct
18 Correct 73 ms 10768 KB Output is correct
19 Correct 94 ms 10468 KB Output is correct
20 Correct 127 ms 13720 KB Output is correct
21 Correct 117 ms 13468 KB Output is correct
22 Correct 119 ms 13504 KB Output is correct