Submission #911477

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
911477	2024-01-19T01:54:45 Z	biank	Mechanical Doll (IOI18_doll)	C++14	16 / 100	112 ms	19036 KB

doll

#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);
    vi 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:59:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   59 |         auto [a,v] = p;
      |              ^

Subtask #1
2.0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	38 ms	9152 KB	Output is correct
3	Correct	35 ms	8792 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	7 ms	1368 KB	Output is correct
6	Correct	61 ms	13260 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	38 ms	9152 KB	Output is correct
3	Correct	35 ms	8792 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	7 ms	1368 KB	Output is correct
6	Correct	61 ms	13260 KB	Output is correct
7	Correct	0 ms	344 KB	Output is correct
8	Correct	64 ms	12400 KB	Output is correct
9	Correct	80 ms	14388 KB	Output is correct
10	Correct	112 ms	19036 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	1 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	38 ms	9152 KB	Output is correct
3	Correct	35 ms	8792 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	7 ms	1368 KB	Output is correct
6	Correct	61 ms	13260 KB	Output is correct
7	Correct	0 ms	344 KB	Output is correct
8	Correct	64 ms	12400 KB	Output is correct
9	Correct	80 ms	14388 KB	Output is correct
10	Correct	112 ms	19036 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	106 ms	16644 KB	Output is correct
15	Correct	58 ms	9672 KB	Output is correct
16	Correct	95 ms	12984 KB	Output is correct
17	Correct	0 ms	432 KB	Output is correct
18	Correct	1 ms	348 KB	Output is correct
19	Correct	1 ms	348 KB	Output is correct
20	Correct	109 ms	16504 KB	Output is correct
21	Correct	1 ms	348 KB	Output is correct
22	Correct	0 ms	348 KB	Output is correct