oj.uz

Submission #417335

# Submission time Handle Problem Language Result Execution time Memory
417335 2021-06-03T14:55:47 Z balbit Mechanical Doll (IOI18_doll) C++14
100 / 100
 159 ms 20884 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
//#define BALBIT
#define ll long long
#define pii pair<int, int>
#define pb push_back
#define f first
#define s second

#define REP(i,n) for (int i = 0; i<n; ++i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)

#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()


#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<"- "<<#__VA_ARGS__<<": ", _do(__VA_ARGS__)

template<typename T> void _do(T && x) { cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S &&...y) {cerr<<x<<", "; _do(y...);}
#else
#define bug(...)

#endif // BALBIT

const int maxn = 2e5+5;

vector<int> go[maxn];

int IT = 0; // keep indexes positive until returning

vector<int> X,Y;
vector<int> sw;
bool st[maxn*4];
bool del[maxn*4];
int par[maxn*4];
bool isx[maxn*4];

//int add(int x=0, int y=0) {
//    X.pb(x); Y.pb(y);
//    return ++IT;
//}

const int inf = 1000000000;

int build(int sz, int bk, int lft) {
    bug(sz,bk,lft);
    if(sz == 0) return bk;
    if (lft == 0) {
//        assert(sz == 1);
        return inf;
    }
    int me = ++IT;
    int bg = min(sz,(1<<(lft-1)));
    X[me] = build(sz-bg, bk, lft-1);
    Y[me] = build(bg, bk, lft-1);
    return -me;
}

void create_circuit(int n, std::vector<int> A) {
    bug("HI");
    X.pb(0); Y.pb(0);
    A.pb(0);
    sw.resize(n+1);
    sw[0] = A[0];
    A.erase(A.begin());
    int m = SZ(A);
    REP(i, m-1) {
        go[A[i]].pb(A[i+1]);
    }
    X.resize(m*2+1); Y.resize(m*2+1);
    int pw = 0;
    while ((1<<pw) < m) ++pw;
    int rt = build(m, -1, pw);
    for (int i = 1; i<=n; ++i) sw[i] = rt==-1?rt:0;
//    assert(rt == -1);
    if (rt == -1) REP(j, m) {
        int at = 1;
        while (1) {
            int &to = st[at]?Y[at]:X[at];
            bug(at, to);
            st[at] ^= 1;
            if (to == inf) {
                to = A[j];
                break;
            }else{
                at = -(to);
            }
        }
    }


    X.erase(X.begin()); Y.erase(Y.begin());
    X.resize(IT); Y.resize(IT);
    answer(sw,X,Y);
}


/*
5 9
1 2 1 3 1 4 1 5 1
*/

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 54 ms 11280 KB Output is correct
3 Correct 50 ms 11096 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 13 ms 6092 KB Output is correct
6 Correct 78 ms 14416 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 54 ms 11280 KB Output is correct
3 Correct 50 ms 11096 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 13 ms 6092 KB Output is correct
6 Correct 78 ms 14416 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Correct 96 ms 15328 KB Output is correct
9 Correct 103 ms 16524 KB Output is correct
10 Correct 159 ms 20884 KB Output is correct
11 Correct 3 ms 4940 KB Output is correct
12 Correct 3 ms 4940 KB Output is correct
13 Correct 3 ms 4940 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 54 ms 11280 KB Output is correct
3 Correct 50 ms 11096 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 13 ms 6092 KB Output is correct
6 Correct 78 ms 14416 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Correct 96 ms 15328 KB Output is correct
9 Correct 103 ms 16524 KB Output is correct
10 Correct 159 ms 20884 KB Output is correct
11 Correct 3 ms 4940 KB Output is correct
12 Correct 3 ms 4940 KB Output is correct
13 Correct 3 ms 4940 KB Output is correct
14 Correct 156 ms 19432 KB Output is correct
15 Correct 95 ms 13756 KB Output is correct
16 Correct 141 ms 18572 KB Output is correct
17 Correct 3 ms 4940 KB Output is correct
18 Correct 3 ms 4940 KB Output is correct
19 Correct 3 ms 4996 KB Output is correct
20 Correct 152 ms 19968 KB Output is correct
21 Correct 3 ms 4940 KB Output is correct
22 Correct 3 ms 4940 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 4 ms 4940 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Correct 3 ms 4920 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 76 ms 11912 KB Output is correct
3 Correct 80 ms 11920 KB Output is correct
4 Correct 134 ms 14884 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 76 ms 11912 KB Output is correct
3 Correct 80 ms 11920 KB Output is correct
4 Correct 134 ms 14884 KB Output is correct
5 Correct 143 ms 17664 KB Output is correct
6 Correct 140 ms 17132 KB Output is correct
7 Correct 142 ms 17268 KB Output is correct
8 Correct 131 ms 16756 KB Output is correct
9 Correct 80 ms 11856 KB Output is correct
10 Correct 135 ms 16244 KB Output is correct
11 Correct 124 ms 16300 KB Output is correct
12 Correct 87 ms 12476 KB Output is correct
13 Correct 88 ms 12924 KB Output is correct
14 Correct 92 ms 12980 KB Output is correct
15 Correct 94 ms 13220 KB Output is correct
16 Correct 5 ms 5196 KB Output is correct
17 Correct 78 ms 12120 KB Output is correct
18 Correct 78 ms 12012 KB Output is correct
19 Correct 82 ms 12092 KB Output is correct
20 Correct 140 ms 16032 KB Output is correct
21 Correct 125 ms 15980 KB Output is correct
22 Correct 127 ms 15628 KB Output is correct