oj.uz

Submission #235681

# Submission time Handle Problem Language Result Execution time Memory
235681 2020-05-29T10:59:57 Z lyc Mechanical Doll (IOI18_doll) C++14
100 / 100
 159 ms 12276 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) //cout << #x << " :: " << x << endl;
#define _ << " " <<
#define FOR(i,a,b) for (int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()

const int mxN = 2e5+5;

int M, N;
int D[2*mxN], L[2*mxN], R[2*mxN], state[2*mxN];

int build(int s, int e, int p, int l) {
    int en = p;
    if (l == 1) R[p] = 1;
    else {
        R[p] = -(p+1);
        en = build(max(s,e-l+1),e,-R[p],l>>1);
    }
    if (e-l >= s) {
        if (l == 1) L[p] = 1;
        else {
            L[p] = -(en+1);
            en = build(s,e-l,-L[p],l>>1);
        }
    } else {
        L[p] = -1;
    }
    TRACE(s _ e _ p _ L[p] _ R[p]);
    return en;
}

void simulate(int p, int v) {
    int pos = p;
    for (;;) {
        //TRACE(pos _ state[-pos]);
        state[-pos] = !state[-pos];
        if (state[-pos]) {
            if (L[-pos] > 0) { TRACE(-pos _ "L" _ v); L[-pos] = v; break; }
            else pos = L[-pos];
        } else {
            if (R[-pos] > 0) { TRACE(-pos _ "R" _ v); R[-pos] = v; break; }
            else pos = R[-pos];
        }
    }
}

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

    int n2 = 1;
    while (n2 < N) n2 <<= 1;
    int S = build(n2-N+1,n2,1,n2>>1);

    for (int& x : A) { simulate(-1,x); }

    vector<int> X(S), Y(S);
    FOR(i,1,S){
        X[i-1] = L[i];
        Y[i-1] = R[i];
        TRACE(i _ X[i-1] _ Y[i-1]);
    }
    answer(C, X, Y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 55 ms 4400 KB Output is correct
3 Correct 45 ms 4668 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1484 KB Output is correct
6 Correct 75 ms 6964 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 55 ms 4400 KB Output is correct
3 Correct 45 ms 4668 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1484 KB Output is correct
6 Correct 75 ms 6964 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 85 ms 8000 KB Output is correct
9 Correct 91 ms 8604 KB Output is correct
10 Correct 157 ms 12276 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 55 ms 4400 KB Output is correct
3 Correct 45 ms 4668 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1484 KB Output is correct
6 Correct 75 ms 6964 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 85 ms 8000 KB Output is correct
9 Correct 91 ms 8604 KB Output is correct
10 Correct 157 ms 12276 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 136 ms 11740 KB Output is correct
15 Correct 112 ms 7476 KB Output is correct
16 Correct 139 ms 11440 KB Output is correct
17 Correct 2 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 142 ms 11936 KB Output is correct
21 Correct 2 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 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 2 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 81 ms 6588 KB Output is correct
3 Correct 78 ms 6592 KB Output is correct
4 Correct 136 ms 10156 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 81 ms 6588 KB Output is correct
3 Correct 78 ms 6592 KB Output is correct
4 Correct 136 ms 10156 KB Output is correct
5 Correct 123 ms 11292 KB Output is correct
6 Correct 159 ms 11020 KB Output is correct
7 Correct 121 ms 11104 KB Output is correct
8 Correct 120 ms 10784 KB Output is correct
9 Correct 82 ms 6552 KB Output is correct
10 Correct 127 ms 10620 KB Output is correct
11 Correct 133 ms 10400 KB Output is correct
12 Correct 82 ms 6848 KB Output is correct
13 Correct 79 ms 7168 KB Output is correct
14 Correct 91 ms 7328 KB Output is correct
15 Correct 82 ms 7484 KB Output is correct
16 Correct 3 ms 460 KB Output is correct
17 Correct 84 ms 6856 KB Output is correct
18 Correct 79 ms 6848 KB Output is correct
19 Correct 92 ms 6828 KB Output is correct
20 Correct 129 ms 10600 KB Output is correct
21 Correct 137 ms 10300 KB Output is correct
22 Correct 124 ms 10348 KB Output is correct