oj.uz

Submission #108204

# Submission time Handle Problem Language Result Execution time Memory
108204 2019-04-28T04:45:06 Z tri Mechanical Doll (IOI18_doll) C++14
100 / 100
 133 ms 19464 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef pair<int, int> pi;
typedef pair<int, vi> ivi;

#define pb push_back
#define f first
#define s second

namespace debug {
    const int DEBUG = false;

    template<class T1, class T2>
    void pr(const pair<T1, T2> &x);

    template<class T, size_t SZ>
    void pr(const array<T, SZ> &x);

    template<class T>
    void pr(const vector<T> &x);

    template<class T>
    void pr(const set<T> &x);

    template<class T1, class T2>
    void pr(const map<T1, T2> &x);

    template<class T>
    void pr(const T &x) { if (DEBUG) cout << x; }

    template<class T, class... Ts>
    void pr(const T &first, const Ts &... rest) { pr(first), pr(rest...); }

    template<class T1, class T2>
    void pr(const pair<T1, T2> &x) { pr("{", x.f, ", ", x.s, "}"); }

    template<class T>
    void prIn(const T &x) {
        pr("{");
        bool fst = 1;
        for (auto &a : x) {
            pr(fst ? "" : ", ", a), fst = 0;
        }
        pr("}");
    }

    template<class T, size_t SZ>
    void pr(const array<T, SZ> &x) { prIn(x); }

    template<class T>
    void pr(const vector<T> &x) { prIn(x); }

    template<class T>
    void pr(const set<T> &x) { prIn(x); }

    template<class T1, class T2>
    void pr(const map<T1, T2> &x) { prIn(x); }

    void ps() { pr("\n"); }

    template<class Arg, class... Args>
    void ps(const Arg &first, const Args &... rest) {
        pr(first, " ");
        ps(rest...);
    }
}

using namespace debug;

void answer(vi C, vi X, vi Y);

vi lk[2]; // if link is negative, is exit
vi p;
vi s;

vi lfV;
vi rmvV;
vi rmvE;

int nxtV = 1;

int N;
int P;

int cns(int cnt, int cP, int cS, int stt, int stp) { // cnt >= 2
    int cV = nxtV++;
    p[cV] = cP;
    s[cV] = cS;

    if (cnt == 2) {
        lk[0][cV] = stt;
        lk[1][cV] = stt + stp;
        lfV.pb(cV);
    } else {
        lk[0][cV] = cns(cnt / 2, cV, 0, stt, stp * 2);
        lk[1][cV] = cns(cnt / 2, cV, 1, stt + stp, stp * 2);
    }
    return cV;
}

void check(int cV) {
    if (cV == -1) {
        return;
    }
    if (rmvV[cV]) {
        return;
    }
    if (lk[0][cV] == lk[1][cV]) {
        int pV = p[cV];
        if (pV == -1) {
            throw "-p";
        }
        lk[s[cV]][pV] = lk[0][cV];

        rmvV[cV] = true;

        check(pV);
    }
}

void create_circuit(int M, vi ord) {
    ord.pb(0); // after visiting all, return to 0

    N = ord.size();
    P = 1 << (32 - __builtin_clz(N - 1)); // smallest pow of 2 greater or equal

    lk[0].resize(2 * N); // construction will not use more than 2*N
    lk[1].resize(2 * N);
    p.resize(2 * N);
    s.resize(2 * N);
    rmvV.resize(2 * N);
    rmvE.resize(P);

    ps("N, P:", N, P);
    cout << flush;
    cns(P, -1, -1, -1, -1); // constructs tree with positive vertices and negative exits

    //ps(lk[0]);
    //ps(lk[1]);
    //ps(p);
    //ps(s);

    int tRmv = P - N;

    for (int i = 0; tRmv; i++) {
        ps(-lk[0][lfV[i]]);
        rmvE[-lk[0][lfV[i]]] = true;
        lk[0][lfV[i]] = 1; // link back exit to root of tree

        if (tRmv >= 2) {
            rmvE[-lk[1][lfV[i]]] = true;
            lk[1][lfV[i]] = 1;
            tRmv -= 2;
        } else {
            tRmv--;
        }
        check(lfV[i]);
    }

    ps(rmvV);
    ps(rmvE);

    ps(lk[0]);
    ps(lk[1]);

    int nxtI = 0;
    vi rE(P + 1);
    for (int i = 1; i <= P; i++) { //note exits actually have negative indices
        if (!rmvE[i]) {
            rE[i] = ord[nxtI++];
        }
    }

    int nRV = -1;
    vi outV(nxtV);
    for (int i = 1; i < nxtV; i++) {
        if (!rmvV[i]) {
            outV[i] = nRV--;
        }
    }

    vi rX(-nRV - 1);
    vi rY(-nRV - 1);

    for (int i = 1; i < nxtV; i++) {
        if (!rmvV[i]) {
            int outCV = -outV[i] - 1;
            if (lk[0][i] > 0) { // links to another vertex
                rX[outCV] = outV[lk[0][i]];
            } else { // is actually an exit
                rX[outCV] = rE[-lk[0][i]];
            }
            if (lk[1][i] > 0) { // links to another vertex
                rY[outCV] = outV[lk[1][i]];
            } else { // is actually an exit
                rY[outCV] = rE[-lk[1][i]];
            }
        }
    }

    vi dir(M + 1);
    for (int i = 0; i <= M; i++) {
        dir[i] = -1;
    }

    answer(dir, rX, rY);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 42 ms 8136 KB Output is correct
3 Correct 39 ms 7752 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 13 ms 1356 KB Output is correct
6 Correct 56 ms 10664 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 42 ms 8136 KB Output is correct
3 Correct 39 ms 7752 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 13 ms 1356 KB Output is correct
6 Correct 56 ms 10664 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 71 ms 14120 KB Output is correct
9 Correct 75 ms 14376 KB Output is correct
10 Correct 103 ms 19464 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 42 ms 8136 KB Output is correct
3 Correct 39 ms 7752 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 13 ms 1356 KB Output is correct
6 Correct 56 ms 10664 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 71 ms 14120 KB Output is correct
9 Correct 75 ms 14376 KB Output is correct
10 Correct 103 ms 19464 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 101 ms 18976 KB Output is correct
15 Correct 75 ms 13604 KB Output is correct
16 Correct 106 ms 18596 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 256 KB Output is correct
19 Correct 1 ms 256 KB Output is correct
20 Correct 95 ms 19104 KB Output is correct
21 Correct 2 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 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 72 ms 13600 KB Output is correct
3 Correct 63 ms 13592 KB Output is correct
4 Correct 91 ms 18400 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 72 ms 13600 KB Output is correct
3 Correct 63 ms 13592 KB Output is correct
4 Correct 91 ms 18400 KB Output is correct
5 Correct 102 ms 18452 KB Output is correct
6 Correct 128 ms 18460 KB Output is correct
7 Correct 90 ms 18480 KB Output is correct
8 Correct 133 ms 18508 KB Output is correct
9 Correct 58 ms 13620 KB Output is correct
10 Correct 87 ms 18468 KB Output is correct
11 Correct 83 ms 18460 KB Output is correct
12 Correct 107 ms 13604 KB Output is correct
13 Correct 62 ms 13632 KB Output is correct
14 Correct 65 ms 13536 KB Output is correct
15 Correct 80 ms 13632 KB Output is correct
16 Correct 3 ms 716 KB Output is correct
17 Correct 60 ms 12476 KB Output is correct
18 Correct 62 ms 13572 KB Output is correct
19 Correct 60 ms 13660 KB Output is correct
20 Correct 122 ms 18472 KB Output is correct
21 Correct 97 ms 18476 KB Output is correct
22 Correct 121 ms 18404 KB Output is correct