oj.uz

Submission #96201

# Submission time Handle Problem Language Result Execution time Memory
96201 2019-02-07T02:02:29 Z lyc Mechanical Doll (IOI18_doll) C++14
53 / 100
 251 ms 112960 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXM = 100005;
deque<int> nxt[MAXM];
int S = -1;
vector<int> C, X, Y;

int bindec(string bin) {
    reverse(bin.begin(), bin.end());
    int dec = 0;
    for (auto c : bin) {
        dec *= 2;
        dec += c-'0';
    }
    //cout << bin << "-> " << dec << endl;
    return dec;
}

void build(int rt, int i, int s, int e, string rec) {
    if (s > e) return;
    
    //cout << "BUILD " << rt << ' ' << i << ' ' << s << ' ' << e << " : " << rec << endl;
    if (s == e) {
        if (i == rt) {
            C[i] = nxt[rt][bindec(rec)];
        }
        else {
            X[-i] = i;
            Y[-i] = nxt[rt][bindec(rec)];
            //X.push_back(rt);
            //Y.push_back(nxt[rt][bindec(rec)]);
        }
    }
    else if (s+1 == e && i != rt) {
        X[-i] = nxt[rt][bindec(rec+'0')];
        Y[-i] = nxt[rt][bindec(rec+'1')];
        //X.push_back(nxt[rt][bindec(rec+'0')]);
        //Y.push_back(nxt[rt][bindec(rec+'1')]);
    }
    else {
        int m = (s+e)/2;
        if (i >= 0) {
            C[i] = S--;
            build(rt, C[i], s, e, rec);
        }
        else {
            int l = S;
            build(rt, S--, s, m, rec+'0');
            int r = S;
            build(rt, S--, m+1, e, rec+'1');
            //X.push_back(l);
            //Y.push_back(r);
            X[-i] = l;
            Y[-i] = r;
            //cout << "BRANCH " << i << " " << X[-i] << " " << Y[-i] << endl;
        }
    }
}

void create_circuit(int M, std::vector<int> A) {
    int N = A.size();
    C.resize(M+1);

    A.push_back(0);
    for (int i = 0; i <= N; ++i) {
        nxt[A[i]].push_back(A[(i+1)%(N+1)]);
    }

    X.resize(2*N);
    Y.resize(2*N);
    for (int i = 0; i <= M; ++i) {
        while (true) {
            int sz = (int)nxt[i].size();
            if (sz - (sz&-sz) > 0) nxt[i].push_front(S);
            else break;
        }
        build(i, i, 0, (int)nxt[i].size()-1, "");
        //cout << i << ": "; for (auto x : nxt[i]) cout << x << ' '; cout << endl;
    }

    vector<int> XX, YY;
    for (int i = 1; i < -S; ++i) {
        XX.push_back(X[i]);
        YY.push_back(Y[i]);
    }
    //cout << endl;
    //for (auto x : C) cout << x << ' '; cout << endl;
    //for (auto x : XX) cout << x << ' '; cout << endl;
    //for (auto x : YY) cout << x << ' '; cout << endl;
    answer(C, XX, YY);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 67524 KB Output is correct
2 Correct 97 ms 70220 KB Output is correct
3 Correct 91 ms 70040 KB Output is correct
4 Correct 56 ms 67504 KB Output is correct
5 Correct 80 ms 68732 KB Output is correct
6 Correct 88 ms 71224 KB Output is correct
7 Correct 54 ms 67600 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 67524 KB Output is correct
2 Correct 97 ms 70220 KB Output is correct
3 Correct 91 ms 70040 KB Output is correct
4 Correct 56 ms 67504 KB Output is correct
5 Correct 80 ms 68732 KB Output is correct
6 Correct 88 ms 71224 KB Output is correct
7 Correct 54 ms 67600 KB Output is correct
8 Correct 106 ms 73748 KB Output is correct
9 Correct 135 ms 73432 KB Output is correct
10 Correct 140 ms 77320 KB Output is correct
11 Correct 61 ms 67536 KB Output is correct
12 Correct 63 ms 67576 KB Output is correct
13 Correct 61 ms 67528 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 67524 KB Output is correct
2 Correct 97 ms 70220 KB Output is correct
3 Correct 91 ms 70040 KB Output is correct
4 Correct 56 ms 67504 KB Output is correct
5 Correct 80 ms 68732 KB Output is correct
6 Correct 88 ms 71224 KB Output is correct
7 Correct 54 ms 67600 KB Output is correct
8 Correct 106 ms 73748 KB Output is correct
9 Correct 135 ms 73432 KB Output is correct
10 Correct 140 ms 77320 KB Output is correct
11 Correct 61 ms 67536 KB Output is correct
12 Correct 63 ms 67576 KB Output is correct
13 Correct 61 ms 67528 KB Output is correct
14 Correct 220 ms 112960 KB Output is correct
15 Correct 127 ms 74424 KB Output is correct
16 Correct 136 ms 76640 KB Output is correct
17 Correct 49 ms 67524 KB Output is correct
18 Correct 53 ms 67480 KB Output is correct
19 Correct 51 ms 67548 KB Output is correct
20 Correct 183 ms 92604 KB Output is correct
21 Correct 57 ms 67512 KB Output is correct
22 Correct 64 ms 67600 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 57 ms 67688 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
9.0000000036 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 48 ms 67576 KB Output is partially correct
2 Correct 140 ms 75340 KB Output is correct
3 Partially correct 189 ms 77976 KB Output is partially correct
4 Partially correct 206 ms 79808 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 48 ms 67576 KB Output is partially correct
2 Correct 140 ms 75340 KB Output is correct
3 Partially correct 189 ms 77976 KB Output is partially correct
4 Partially correct 206 ms 79808 KB Output is partially correct
5 Partially correct 234 ms 100132 KB Output is partially correct
6 Partially correct 216 ms 92052 KB Output is partially correct
7 Partially correct 216 ms 94648 KB Output is partially correct
8 Partially correct 200 ms 87260 KB Output is partially correct
9 Partially correct 203 ms 78092 KB Output is partially correct
10 Partially correct 251 ms 86296 KB Output is partially correct
11 Partially correct 225 ms 84648 KB Output is partially correct
12 Partially correct 164 ms 77956 KB Output is partially correct
13 Partially correct 147 ms 83532 KB Output is partially correct
14 Partially correct 160 ms 85488 KB Output is partially correct
15 Partially correct 151 ms 88864 KB Output is partially correct
16 Partially correct 63 ms 67864 KB Output is partially correct
17 Partially correct 135 ms 76240 KB Output is partially correct
18 Partially correct 140 ms 76396 KB Output is partially correct
19 Partially correct 134 ms 76740 KB Output is partially correct
20 Partially correct 179 ms 80600 KB Output is partially correct
21 Partially correct 182 ms 81752 KB Output is partially correct
22 Partially correct 160 ms 79628 KB Output is partially correct