oj.uz

Submission #1024285

# Submission time Handle Problem Language Result Execution time Memory
1024285 2024-07-15T23:06:05 Z efishel Mechanical Doll (IOI18_doll) C++17
84 / 100
 112 ms 38708 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using vi = vector <int>;

struct Switch {
    Switch *x, *y;
    bool pointX;
    ll id;
    ll in, act;
    bool isEnd;
    bool isAct;

    Switch (ll in, ll act): x(0), y(0), pointX(true), in(in), act(act), isEnd(false) {
        if (act == 0) { isEnd = true; isAct = false; return; }
        if (act == 1 && in == 1) { isEnd = true; isAct = true; return; }
        ll goR = min(in/2, act);
        x = new Switch(in/2, act-goR);
        y = new Switch(in/2, goR);
    }

    ll dfs (ll &timer, vll &toX, vll &toY) {
        if (isEnd) return 15;
        id = timer--;
        toX[-id-1] = x->dfs(timer, toX, toY);
        toY[-id-1] = y->dfs(timer, toX, toY);
        return id;
    }

    pair <ll, ll> trig (ll par, ll st) {
        if (isEnd) return isAct ? pair <ll, ll>{ par, st } : pair <ll, ll>{ par, st+2 };
        if (pointX ^= 1)
            return y->trig(id, 0);
        else
            return x->trig(id, 1);
    }
};

void create_circuit (int m, vi A) {
    vll ve(A.begin(), A.end());
    ve.push_back(0);
    ll n = ve.size();
    ll pow2 = 2<<__lg(n-1);
    ll timer = -1;
    Switch root(pow2, n);
    vll toX(pow2, 15), toY(pow2, 15);
    ll rootId = root.dfs(timer, toX, toY);
    ll c = 0;
    for (ll i = 0; i < pow2; i++) {
        auto [a, st] = root.trig(17, false);
        a = -a-1;
        if (st >= 2) {
            (st-2 ? toX : toY)[a] = rootId;
            continue;
        }
        (st ? toX : toY)[a] = ve[c];
        c++;
    }
    ll sz = -min(*min_element(toX.begin(), toX.end()), *min_element(toY.begin(), toY.end()));
    toX.resize(sz);
    toY.resize(sz);
    answer(vi(m+1, -1), vi(toX.begin(), toX.end()), vi(toY.begin(), toY.end()));
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 36 ms 13864 KB Output is correct
3 Correct 35 ms 13692 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 5 ms 1116 KB Output is correct
6 Correct 51 ms 19524 KB Output is correct
7 Incorrect 0 ms 348 KB wrong serial number
8 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 36 ms 13864 KB Output is correct
3 Correct 35 ms 13692 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 5 ms 1116 KB Output is correct
6 Correct 51 ms 19524 KB Output is correct
7 Incorrect 0 ms 348 KB wrong serial number
8 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 36 ms 13864 KB Output is correct
3 Correct 35 ms 13692 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 5 ms 1116 KB Output is correct
6 Correct 51 ms 19524 KB Output is correct
7 Incorrect 0 ms 348 KB wrong serial number
8 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 74 ms 25864 KB Output is correct
3 Correct 68 ms 25932 KB Output is correct
4 Correct 96 ms 37176 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 74 ms 25864 KB Output is correct
3 Correct 68 ms 25932 KB Output is correct
4 Correct 96 ms 37176 KB Output is correct
5 Correct 104 ms 38200 KB Output is correct
6 Correct 107 ms 37428 KB Output is correct
7 Correct 104 ms 37432 KB Output is correct
8 Correct 96 ms 38684 KB Output is correct
9 Correct 68 ms 25756 KB Output is correct
10 Correct 102 ms 38456 KB Output is correct
11 Correct 102 ms 38468 KB Output is correct
12 Correct 67 ms 25908 KB Output is correct
13 Correct 70 ms 25892 KB Output is correct
14 Correct 68 ms 25936 KB Output is correct
15 Correct 66 ms 26192 KB Output is correct
16 Correct 2 ms 1112 KB Output is correct
17 Correct 64 ms 23844 KB Output is correct
18 Correct 65 ms 26000 KB Output is correct
19 Correct 66 ms 25844 KB Output is correct
20 Correct 107 ms 38196 KB Output is correct
21 Correct 112 ms 38708 KB Output is correct
22 Correct 99 ms 37812 KB Output is correct