제출 #764662

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
764662		MetalPower	자동 인형 (IOI18_doll)	C++14	100 / 100	200 ms	29924 KiB

doll

#include "doll.h"

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

const int MX = 3e5 + 10;

int cnt[MX];
map<int, int> lf, rg;
vector<int> nx;

int _M, huge_mask = 0, tim = 0, mx_idx = 0;
vector<int> pos_starts;

int solve(int idx, int mask){
	if(idx > 0 && !(huge_mask >> (mx_idx - idx) & 1)){
		huge_mask ^= 1 << (mx_idx - idx);
		return -1;
	}else if(idx == mx_idx){
		pos_starts.push_back(mask);
		return 2 * _M + mask + 10;
	}else{
		++tim; int curr = -tim;
		lf[curr] = solve(idx + 1, mask);
		rg[curr] = solve(idx + 1, mask + (1 << idx));
		return curr;
	}
}

void create_circuit(int M, vector<int> A) {

	_M = M;
	int N = A.size();
	vector<int> C(M + 1), X, Y;

	if(N == 1){
		C[0] = A[0];
		for(int i = 1; i <= M; i++) C[i] = 0;
		answer(C, X, Y);
		return;
	}
	
	C[0] = A[0]; cnt[A[0]]++;
	for(int i = 1; i < N; i++) cnt[A[i]]++, nx.push_back(A[i]);
	nx.push_back(0);

	huge_mask = N - 1;
	for(int j = 0; j < 20; j++){
		if((1 << j) > huge_mask){
			mx_idx = j;
			break;
		}
	}

	for(int i = 1; i <= M; i++){
		if(cnt[i] == 0) C[i] = 0;
		else C[i] = -1;
	}

	solve(0, 0);
	sort(pos_starts.begin(), pos_starts.end());

	for(int i = -1; i >= -tim; i--){
		if(lf[i] > M){
			int curr_mask = lf[i] - 2 * M - 10;
			int idx = lower_bound(pos_starts.begin(), pos_starts.end(), curr_mask) - pos_starts.begin();
			X.push_back(nx[idx]);
		}else{
			X.push_back(lf[i]);
		}
		if(rg[i] > M){
			int curr_mask = rg[i] - 2 * M - 10;
			int idx = lower_bound(pos_starts.begin(), pos_starts.end(), curr_mask) - pos_starts.begin();
			Y.push_back(nx[idx]);
		}else{
			Y.push_back(rg[i]);
		}
	}

	answer(C, X, Y);
}

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