oj.uz

Submission #911727

# Submission time Handle Problem Language Result Execution time Memory
911727 2024-01-19T04:58:06 Z biank Mechanical Doll (IOI18_doll) C++14
100 / 100
 167 ms 16064 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, skip, s;

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;
    build(L[u]=t++,l,m);
    build(R[u]=t++,m,r);
}
     
void dfs(int u, int a) {
    if(u&&v[u]==-1) dfs(0,a);
    else if(!v[u]) v[u]=a;
    else if(state[u]^=1) dfs(L[u],a);
    else dfs(R[u],a);
}
     
void create_circuit(int m, vi a) {
    vi c(m+1), x, y;
    c[0]=a[0];
    int n=SIZE(a),sz=1;
    if(n==1) return answer(c,x,y);
    forsn(i,1,m+1) c[i]=-1;
    while(sz<n) sz*=2;
    skip=sz-n;
    build(t++,0,sz);
    a.pb(0),state.assign(t,0);
    forsn(i,1,n+1) 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 0 ms 344 KB Output is correct
2 Correct 41 ms 5832 KB Output is correct
3 Correct 37 ms 6320 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 9 ms 1372 KB Output is correct
6 Correct 61 ms 8964 KB Output is correct
7 Correct 0 ms 344 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 41 ms 5832 KB Output is correct
3 Correct 37 ms 6320 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 9 ms 1372 KB Output is correct
6 Correct 61 ms 8964 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 72 ms 10652 KB Output is correct
9 Correct 71 ms 11812 KB Output is correct
10 Correct 117 ms 16064 KB Output is correct
11 Correct 0 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 0 ms 344 KB Output is correct
2 Correct 41 ms 5832 KB Output is correct
3 Correct 37 ms 6320 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 9 ms 1372 KB Output is correct
6 Correct 61 ms 8964 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 72 ms 10652 KB Output is correct
9 Correct 71 ms 11812 KB Output is correct
10 Correct 117 ms 16064 KB Output is correct
11 Correct 0 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 109 ms 15492 KB Output is correct
15 Correct 65 ms 10712 KB Output is correct
16 Correct 120 ms 15552 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 111 ms 15924 KB Output is correct
21 Correct 0 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 1 ms 344 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 73 ms 9624 KB Output is correct
3 Correct 60 ms 10156 KB Output is correct
4 Correct 106 ms 14476 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 73 ms 9624 KB Output is correct
3 Correct 60 ms 10156 KB Output is correct
4 Correct 106 ms 14476 KB Output is correct
5 Correct 150 ms 15320 KB Output is correct
6 Correct 110 ms 15500 KB Output is correct
7 Correct 123 ms 15532 KB Output is correct
8 Correct 126 ms 15360 KB Output is correct
9 Correct 60 ms 10148 KB Output is correct
10 Correct 109 ms 15216 KB Output is correct
11 Correct 167 ms 14976 KB Output is correct
12 Correct 72 ms 10256 KB Output is correct
13 Correct 83 ms 10128 KB Output is correct
14 Correct 64 ms 10784 KB Output is correct
15 Correct 72 ms 10784 KB Output is correct
16 Correct 2 ms 604 KB Output is correct
17 Correct 66 ms 9804 KB Output is correct
18 Correct 68 ms 9648 KB Output is correct
19 Correct 64 ms 10544 KB Output is correct
20 Correct 103 ms 15108 KB Output is correct
21 Correct 106 ms 14984 KB Output is correct
22 Correct 109 ms 14984 KB Output is correct