제출 #1282063

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1282063		WH8	자동 인형 (IOI18_doll)	C++20	100 / 100	96 ms	13976 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

void create_circuit(int M, vector<int> A) {
	int n = A.size();
	vector<int> C(M + 1);
	C[0] = -1;
	for (int i = 1; i <= M; ++i) {
		C[i] = -1;
	}
	int tar=1;
	while(tar < n+1){
		tar*=2;
	}
	A.push_back(0);
	while((int)A.size()<tar){
		A.push_back(-1);
	}
	int nw=1;
	vector<int> X(2*n, 1e9), Y(2*n, 1e9);
	vector<int> in;
	vector<int> lol={-1};
	auto dfs=[&](auto && dfs, int s, int e, vector<int> v)->int {
		vector<int> l, r;
		int m=(s+e)/2;
		assert((int)v.size()==e-s+1);
		//~ printf("node %d to %d, \n", s,e);
		//~ for(auto it: v)cout<<it<<" ";
		//~ cout<<endl;
		for(int i=0;i<(int)v.size();i++){
			if(i%2==0)l.push_back(v[i]);
			else r.push_back(v[i]);
		}
		if(e <= tar-n-1){
			return -1;
		}
		else {
			if(s==e){
				lol.push_back(v[0]);
				return v[0];
			}
			int cn=nw;
			nw++;
			if(m <= tar-n-1){
				X[cn]=-1;
			}
			else {
				X[cn]=dfs(dfs, s, m,l);
			}
			Y[cn]=dfs(dfs, m+1, e, r);
			return -cn;
		}
	};
	vector<int> temp(A.size());
	iota(temp.begin(),temp.end(),1);
	dfs(dfs, 1, (int)temp.size(), temp);
	vector<int> ansx, ansy;
	sort(lol.begin(),lol.end());
	//~ for(auto ind : lol){
		//~ cout<<ind<<endl;
	//~ }
	//~ assert((int)lol.size()==n+2);
	auto conv=[&](int x)->int{
		if(x <= 0)return x;
		int ind=lower_bound(lol.begin(),lol.end(),x) -lol.begin();
		//~ printf("conv %d , res ind %d\n", x, ind);
		return A[ind-1];
	};
	for(int i=1;i<nw;i++){
		ansx.push_back(conv(X[i]));
		ansy.push_back(conv(Y[i]));
		//~ printf("switch %d X %d Y %d\n", -i, conv(X[i]), conv(Y[i]));

		
	}
	answer(C, ansx, ansy);
}
/*
	4 4
	1 2 1 3
*/

• Subtask 1: 2 / 2
• Subtask 2: 4 / 4
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 18 / 18
• Subtask 6: 56 / 56