oj.uz

Submission #911701

# Submission time Handle Problem Language Result Execution time Memory
911701 2024-01-19T04:46:04 Z biank Mechanical Doll (IOI18_doll) C++14
100 / 100
 158 ms 16252 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);
}
     
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 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) 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 348 KB Output is correct
2 Correct 39 ms 5904 KB Output is correct
3 Correct 33 ms 6320 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 7 ms 1624 KB Output is correct
6 Correct 56 ms 9248 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 0 ms 348 KB Output is correct
2 Correct 39 ms 5904 KB Output is correct
3 Correct 33 ms 6320 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 7 ms 1624 KB Output is correct
6 Correct 56 ms 9248 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 70 ms 10512 KB Output is correct
9 Correct 69 ms 11804 KB Output is correct
10 Correct 121 ms 16252 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 348 KB Output is correct
2 Correct 39 ms 5904 KB Output is correct
3 Correct 33 ms 6320 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 7 ms 1624 KB Output is correct
6 Correct 56 ms 9248 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 70 ms 10512 KB Output is correct
9 Correct 69 ms 11804 KB Output is correct
10 Correct 121 ms 16252 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 15624 KB Output is correct
15 Correct 61 ms 10792 KB Output is correct
16 Correct 107 ms 15560 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 109 ms 16016 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 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 376 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 348 KB Output is correct
2 Correct 65 ms 9548 KB Output is correct
3 Correct 59 ms 10148 KB Output is correct
4 Correct 106 ms 14540 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 65 ms 9548 KB Output is correct
3 Correct 59 ms 10148 KB Output is correct
4 Correct 106 ms 14540 KB Output is correct
5 Correct 158 ms 15340 KB Output is correct
6 Correct 108 ms 15540 KB Output is correct
7 Correct 106 ms 15348 KB Output is correct
8 Correct 120 ms 15360 KB Output is correct
9 Correct 69 ms 10140 KB Output is correct
10 Correct 104 ms 15196 KB Output is correct
11 Correct 139 ms 14840 KB Output is correct
12 Correct 72 ms 10452 KB Output is correct
13 Correct 66 ms 10132 KB Output is correct
14 Correct 67 ms 10744 KB Output is correct
15 Correct 66 ms 10780 KB Output is correct
16 Correct 2 ms 604 KB Output is correct
17 Correct 65 ms 9908 KB Output is correct
18 Correct 66 ms 9648 KB Output is correct
19 Correct 65 ms 10372 KB Output is correct
20 Correct 115 ms 15108 KB Output is correct
21 Correct 99 ms 14776 KB Output is correct
22 Correct 103 ms 15532 KB Output is correct