oj.uz

Submission #911653

# Submission time Handle Problem Language Result Execution time Memory
911653 2024-01-19T04:28:20 Z biank Mechanical Doll (IOI18_doll) C++14
100 / 100
 189 ms 17352 KB 
#include <bits/stdc++.h>
#include "doll.h"
using namespace std;
#define SIZE(x) (int)x.size()
#define forn(i,n) for(int i=0;i<int(n);i++)
#define forsn(i,s,n) for(int i=int(s);i<int(n);i++)
#define pb push_back
typedef vector<int> vi;
         
vi L, R, v, state;
int t=1, skip, s=-1;
     
void build(int u, int l, int r) {
    L.pb(0), R.pb(0), v.pb(0);
    if(r-l<=skip) {
        v[u]=-1;
        skip-=r-l;
        return;
    }
    if(r-l==1) return;
    v[u] = s--;
    int m=(l+r)/2;
    L[u] = t++;
    build(L[u], l, m);
    R[u] = t++;
    build(R[u], m, r);
}
     
bool dfs(int u, int a) {
    if(u && v[u]==-1) return false;
    if(!v[u]) {
        v[u]=a;
        return true;
    }
    state[u]^=1;
    if(state[u]) return dfs(L[u],a);
    return dfs(R[u],a);
}
     
void create_circuit(int m, vi A) {
    vi c(m+1,0), x, y;
    c[0]=A[0];
    int n=SIZE(A);
    if(n==1) {
        answer(c,x,y);
        return;
    }
    forsn(i,1,m+1) c[i]=-1;
    int sz=1;
    while(sz<n) sz*=2;
    skip = sz-n;
    build(0,0,sz);
    vi a;
    forsn(i,1,n) a.pb(A[i]);
    a.pb(0);
    state.assign(SIZE(v),0);
    forn(i,n) while(!dfs(0,a[i]));
    forn(i,SIZE(v)) {
        if(L[i] || R[i]) {
            x.pb(v[L[i]]);
            y.pb(v[R[i]]);
        }
    }
    answer(c,x,y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 41 ms 6240 KB Output is correct
3 Correct 34 ms 6320 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 8 ms 1372 KB Output is correct
6 Correct 55 ms 9328 KB Output is correct
7 Correct 1 ms 348 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 41 ms 6240 KB Output is correct
3 Correct 34 ms 6320 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 8 ms 1372 KB Output is correct
6 Correct 55 ms 9328 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 71 ms 11248 KB Output is correct
9 Correct 71 ms 11488 KB Output is correct
10 Correct 108 ms 17352 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 41 ms 6240 KB Output is correct
3 Correct 34 ms 6320 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 8 ms 1372 KB Output is correct
6 Correct 55 ms 9328 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 71 ms 11248 KB Output is correct
9 Correct 71 ms 11488 KB Output is correct
10 Correct 108 ms 17352 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 103 ms 16792 KB Output is correct
15 Correct 64 ms 11296 KB Output is correct
16 Correct 146 ms 16464 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 108 ms 16864 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 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 1 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 66 ms 10452 KB Output is correct
3 Correct 81 ms 10660 KB Output is correct
4 Correct 127 ms 15440 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 66 ms 10452 KB Output is correct
3 Correct 81 ms 10660 KB Output is correct
4 Correct 127 ms 15440 KB Output is correct
5 Correct 117 ms 16400 KB Output is correct
6 Correct 110 ms 16288 KB Output is correct
7 Correct 115 ms 16408 KB Output is correct
8 Correct 141 ms 16280 KB Output is correct
9 Correct 65 ms 10664 KB Output is correct
10 Correct 134 ms 16236 KB Output is correct
11 Correct 129 ms 15960 KB Output is correct
12 Correct 65 ms 10920 KB Output is correct
13 Correct 79 ms 11008 KB Output is correct
14 Correct 93 ms 11300 KB Output is correct
15 Correct 66 ms 11768 KB Output is correct
16 Correct 2 ms 604 KB Output is correct
17 Correct 67 ms 10712 KB Output is correct
18 Correct 72 ms 10716 KB Output is correct
19 Correct 64 ms 10916 KB Output is correct
20 Correct 189 ms 15964 KB Output is correct
21 Correct 159 ms 15944 KB Output is correct
22 Correct 154 ms 15792 KB Output is correct