oj.uz

Submission #911680

# Submission time Handle Problem Language Result Execution time Memory
911680 2024-01-19T04:36:31 Z biank Mechanical Doll (IOI18_doll) C++14
100 / 100
 111 ms 16088 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;
    }
    if(state[u]^=1) 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);
    a.pb(0);
    state.assign(SIZE(v),0);
    forsn(i,1,n+1) while(!dfs(0,a[i]));
    forn(i,t) {
        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 344 KB Output is correct
2 Correct 39 ms 5836 KB Output is correct
3 Correct 34 ms 6324 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 8 ms 1372 KB Output is correct
6 Correct 63 ms 9052 KB Output is correct
7 Correct 0 ms 348 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 39 ms 5836 KB Output is correct
3 Correct 34 ms 6324 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 8 ms 1372 KB Output is correct
6 Correct 63 ms 9052 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 75 ms 10588 KB Output is correct
9 Correct 70 ms 11736 KB Output is correct
10 Correct 106 ms 16088 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 344 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 344 KB Output is correct
2 Correct 39 ms 5836 KB Output is correct
3 Correct 34 ms 6324 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 8 ms 1372 KB Output is correct
6 Correct 63 ms 9052 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 75 ms 10588 KB Output is correct
9 Correct 70 ms 11736 KB Output is correct
10 Correct 106 ms 16088 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 107 ms 15580 KB Output is correct
15 Correct 69 ms 10964 KB Output is correct
16 Correct 111 ms 15560 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 600 KB Output is correct
20 Correct 108 ms 15836 KB Output is correct
21 Correct 0 ms 344 KB Output is correct
22 Correct 0 ms 344 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 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 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 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 9652 KB Output is correct
3 Correct 63 ms 10156 KB Output is correct
4 Correct 101 ms 14524 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 9652 KB Output is correct
3 Correct 63 ms 10156 KB Output is correct
4 Correct 101 ms 14524 KB Output is correct
5 Correct 104 ms 15340 KB Output is correct
6 Correct 101 ms 15468 KB Output is correct
7 Correct 111 ms 15536 KB Output is correct
8 Correct 102 ms 15360 KB Output is correct
9 Correct 61 ms 10212 KB Output is correct
10 Correct 103 ms 15228 KB Output is correct
11 Correct 101 ms 14984 KB Output is correct
12 Correct 62 ms 10404 KB Output is correct
13 Correct 67 ms 10024 KB Output is correct
14 Correct 65 ms 10632 KB Output is correct
15 Correct 64 ms 10824 KB Output is correct
16 Correct 2 ms 600 KB Output is correct
17 Correct 66 ms 9904 KB Output is correct
18 Correct 66 ms 9980 KB Output is correct
19 Correct 63 ms 10452 KB Output is correct
20 Correct 102 ms 15108 KB Output is correct
21 Correct 103 ms 14784 KB Output is correct
22 Correct 104 ms 14992 KB Output is correct