답안 #911477

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
911477	2024-01-19T01:54:45 Z	biank	자동 인형 (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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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