oj.uz

Submission #911493

# Submission time Handle Problem Language Result Execution time Memory
911493 2024-01-19T02:11:01 Z biank Mechanical Doll (IOI18_doll) C++14
100 / 100
 136 ms 22144 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(l>r) {
        v[u]=-1;
        return;
    }
    if(skip>0 && r-l+1<=skip) {
        v[u]=-1;
        skip-=r-l+1;
        return;
    }
    if(l==r) return;
    v[u] = s--;
    int m=(l+r)/2;
    L[u] = t++;
    build(L[u], l, m);
    R[u] = t++;
    build(R[u], m+1, 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,1,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);
}

Compilation message

doll.cpp: In function 'bool first_subtasks(int, vi)':
doll.cpp:58:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   58 |         auto [a,v] = p;
      |              ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 38 ms 9560 KB Output is correct
3 Correct 34 ms 9300 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 7 ms 1624 KB Output is correct
6 Correct 63 ms 13604 KB Output is correct
7 Correct 1 ms 344 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 38 ms 9560 KB Output is correct
3 Correct 34 ms 9300 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 7 ms 1624 KB Output is correct
6 Correct 63 ms 13604 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 72 ms 11424 KB Output is correct
9 Correct 77 ms 13740 KB Output is correct
10 Correct 113 ms 17676 KB Output is correct
11 Correct 1 ms 600 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 500 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 38 ms 9560 KB Output is correct
3 Correct 34 ms 9300 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 7 ms 1624 KB Output is correct
6 Correct 63 ms 13604 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 72 ms 11424 KB Output is correct
9 Correct 77 ms 13740 KB Output is correct
10 Correct 113 ms 17676 KB Output is correct
11 Correct 1 ms 600 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 500 KB Output is correct
14 Correct 132 ms 15360 KB Output is correct
15 Correct 60 ms 8556 KB Output is correct
16 Correct 88 ms 12352 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 104 ms 15684 KB Output is correct
21 Correct 1 ms 348 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 0 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 0 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 0 ms 348 KB Output is correct
2 Correct 58 ms 10480 KB Output is correct
3 Correct 61 ms 10888 KB Output is correct
4 Correct 88 ms 16148 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 58 ms 10480 KB Output is correct
3 Correct 61 ms 10888 KB Output is correct
4 Correct 88 ms 16148 KB Output is correct
5 Correct 136 ms 22144 KB Output is correct
6 Correct 134 ms 20264 KB Output is correct
7 Correct 130 ms 20764 KB Output is correct
8 Correct 121 ms 19740 KB Output is correct
9 Correct 59 ms 10724 KB Output is correct
10 Correct 104 ms 19032 KB Output is correct
11 Correct 101 ms 17004 KB Output is correct
12 Correct 67 ms 11620 KB Output is correct
13 Correct 81 ms 12608 KB Output is correct
14 Correct 85 ms 14272 KB Output is correct
15 Correct 94 ms 14676 KB Output is correct
16 Correct 2 ms 856 KB Output is correct
17 Correct 66 ms 11176 KB Output is correct
18 Correct 73 ms 10804 KB Output is correct
19 Correct 67 ms 11684 KB Output is correct
20 Correct 113 ms 18616 KB Output is correct
21 Correct 112 ms 16672 KB Output is correct
22 Correct 106 ms 18464 KB Output is correct