oj.uz

Submission #911535

# Submission time Handle Problem Language Result Execution time Memory
911535 2024-01-19T03:21:12 Z biank Mechanical Doll (IOI18_doll) C++17
100 / 100
 172 ms 22168 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);
    assert(u>=0 && u<SIZE(v));
    if(r<=l) {
        v[u]=-1;
        return;
    }
    if(skip>0 && 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) {
    assert(u>=0 && u<SIZE(v));
    if(u!=0 && v[u]==-1) return false;
    if(!v[u]) {
        v[u]=a;
        return true;
    }
    state[u]^=1;
    assert(v[L[u]]!=-1 || v[R[u]]!=-1);
    if(state[u]) return dfs(L[u],a);
    return dfs(R[u],a);
}

bool first_subtasks(int m, vi a) {
    vi c(m+1),x,y;
    
    map<int,vi> next;
    int n=SIZE(a);
    a.pb(0);
    forn(i,n) next[a[i]].pb(a[i+1]);
    
    c[0]=a[0];
    int j=0;
    for(auto &p:next) {
        auto [a,v] = p;
        int S=SIZE(v);
        if(S==1) {
            c[a] = v[0];
        } else if(S==2) {
            c[a] = --j;
            x.pb(v[0]);
            y.pb(v[1]);
            continue;
        } else if(S==4) {
            c[a] = --j;
            x.pb(--j);
            y.pb(--j);
            x.pb(v[0]);
            y.pb(v[2]);
            x.pb(v[1]);
            y.pb(v[3]);
            continue;
        } else if(S==3) {
            c[a] = --j;
            x.pb(--j);
            y.pb(--j);
            x.pb(v[0]);
            y.pb(v[1]);
            x.pb(j+2);
            y.pb(v[2]);
        } else {
            return false;
        }
    }
    answer(c,x,y);
    return true;
}
     
void create_circuit(int m, vi A) {
    if(first_subtasks(m,A)) return;
    vi c(m+1);
    c[0]=A[0];
    forsn(i,1,m+1) c[i]=-1;
    int n=SIZE(A), sz=1;
    while(sz<n) sz*=2;
    assert(sz>=n);
    skip = sz-n;
    build(0,0,sz);
    assert(SIZE(L)==SIZE(R) && SIZE(v)==SIZE(L));
    vi a;
    forsn(i,1,n) a.pb(A[i]);
    a.pb(0);
    state.assign(SIZE(v),0);
    forn(i,n) {
        bool flag=0;
        while(!flag) flag=dfs(0,a[i]);
    }
    vi x, y;
    int mini=-1;
    forn(i,SIZE(v)) {
        if(L[i] && R[i]) {
            x.pb(v[L[i]]);
            y.pb(v[R[i]]);
            mini=min({mini,v[L[i]],v[R[i]]});
        }
    }
    if(SIZE(x)<-mini) {
        x.resize(-mini,-1);
        y.resize(-mini,-1);
    }
    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 42 ms 9548 KB Output is correct
3 Correct 38 ms 9000 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 7 ms 1372 KB Output is correct
6 Correct 93 ms 13568 KB Output is correct
7 Correct 1 ms 600 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 42 ms 9548 KB Output is correct
3 Correct 38 ms 9000 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 7 ms 1372 KB Output is correct
6 Correct 93 ms 13568 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 77 ms 12488 KB Output is correct
9 Correct 133 ms 14764 KB Output is correct
10 Correct 126 ms 19088 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 436 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 42 ms 9548 KB Output is correct
3 Correct 38 ms 9000 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 7 ms 1372 KB Output is correct
6 Correct 93 ms 13568 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 77 ms 12488 KB Output is correct
9 Correct 133 ms 14764 KB Output is correct
10 Correct 126 ms 19088 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 436 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 125 ms 16964 KB Output is correct
15 Correct 71 ms 9556 KB Output is correct
16 Correct 125 ms 13636 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 160 ms 17184 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 1 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 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 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 63 ms 10524 KB Output is correct
3 Correct 63 ms 10820 KB Output is correct
4 Correct 108 ms 16136 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 63 ms 10524 KB Output is correct
3 Correct 63 ms 10820 KB Output is correct
4 Correct 108 ms 16136 KB Output is correct
5 Correct 157 ms 22168 KB Output is correct
6 Correct 153 ms 20424 KB Output is correct
7 Correct 172 ms 20748 KB Output is correct
8 Correct 148 ms 19788 KB Output is correct
9 Correct 60 ms 10720 KB Output is correct
10 Correct 123 ms 19080 KB Output is correct
11 Correct 101 ms 16928 KB Output is correct
12 Correct 70 ms 11712 KB Output is correct
13 Correct 88 ms 12852 KB Output is correct
14 Correct 107 ms 14268 KB Output is correct
15 Correct 91 ms 14780 KB Output is correct
16 Correct 2 ms 860 KB Output is correct
17 Correct 72 ms 11332 KB Output is correct
18 Correct 66 ms 10816 KB Output is correct
19 Correct 80 ms 12056 KB Output is correct
20 Correct 115 ms 18716 KB Output is correct
21 Correct 115 ms 16888 KB Output is correct
22 Correct 124 ms 18432 KB Output is correct