제출 #198502

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
198502		SuperJava	자동 인형 (IOI18_doll)	C++17	62.00 / 100	237 ms	25080 KiB

doll

#include "doll.h"
#include <vector>
#include <utility>
#include <iostream>
#include <algorithm>
#include <map>
#define sz(A) int(size(A))
using namespace std;

vector<int> adj[200005];
vector<int> v = {2,4,8,16,32,64,128,256,512,1024,2048,
				4096,8192,16384,32768,65536,131072,
				262144};

int dig(int x){
	int ans = 0;
	while(x != 1){
		x /= 2;
		ans++;
	}
	return ans;
}

void create_circuit(int M, vector<int> A) {
	for(int i = 0; i < sz(A)-1; i++){
		adj[A[i]].push_back(A[i+1]);
	}
	adj[A[sz(A)-1]].push_back(0);
	vector<int> C(M+1);
	C[0] = A[0];
	vector<int> X,Y;
	for(int i = 1; i <= M; i++){
		int w = sz(adj[i]);
		if(w == 0) continue;
		if(w == 1){
			C[i] = adj[i][0];
			continue;
		}
		if(w == 2){
			C[i] = -(sz(X)+1);
			X.push_back(adj[i][0]);
			Y.push_back(adj[i][1]);
			continue;
		}
		if((w&(w-1))){
			C[i] = -(sz(X)+1);
			int fulen = *lower_bound(v.begin(), v.end(),w);
			vector<pair<int,int>> news(fulen-1);
			for(int j = 0; j < fulen/2-1; j++){
				news[j].first = -(j+1)*2-sz(X);
				news[j].second = -(j+1)*2-sz(X)-1;
			}
			int digits = dig(fulen);
			vector<int> toadd(w);
			for(int j = 0; j < w; j++){
				toadd[j] = adj[i][j];
			}
			vector<int> qw;
			for(int j = 0; j < fulen; j++){
				int res = 0;
				for(int k = 0; k < digits; k++){
					res += (1<<k)*((j&(1<<(digits-k-1))) > 0);
				}
				qw.push_back(res);
			}
			for(int j = 0; j < fulen-w; j++){
				if(j&1){
					news[j/2+fulen/2-1].second = -(sz(X)+1);
				}else{
					news[j/2+fulen/2-1].first = -(sz(X)+1);
				}
			}
			vector<pair<int,int>> ss;
			for(int j = fulen-w; j < fulen; j++){
				ss.push_back({qw[j],j});
			}
			sort(ss.begin(), ss.end());
			for(int j = 0; j < w; j++){
				if(ss[j].second&1){
					news[(ss[j].second/2+fulen/2-1)].second = toadd[j];
				}else{
					news[(ss[j].second/2+fulen/2-1)].first = toadd[j];
				}
			}
			for(int j = fulen-2; j >= 0; j--){
				if(news[j].first == -(sz(X)+1) && news[j].second == -(sz(X)+1)){
					if(j&1){
						news[(j+1)/2-1].first = -(sz(X)+1);
					}else{
						news[(j+1)/2-1].second = -(sz(X)+1);
					}
				}
			}
			map<int,int> m;
			int counter = -(sz(X)+1);
			for(int j = 0; j < sz(news); j++){
				if(news[j].first == -1 && news[j].second == -1) continue;
				m[-j-(sz(X)+1)] = counter--;
			}
			for(int j = 0; j < sz(news); j++){
				if(news[j].first == -1 && news[j].second == -1) continue;
				if(news[j].first < 0) news[j].first = m[news[j].first];
				if(news[j].second < 0) news[j].second = m[news[j].second];
			}
			for(int j = 0; j < sz(news); j++){
				if(news[j].first == -1 && news[j].second == -1) continue;
			//	cout << news[j].first << " " << news[j].second << endl;
			}
			for(int j = 0; j < fulen-1; j++){
				if(news[j].first == -1 && news[j].second == -1) continue;
				X.push_back(news[j].first);
				Y.push_back(news[j].second);
			}
		}else{
			C[i] = -(sz(X)+1);
			int fulen = *lower_bound(v.begin(), v.end(),w);
			vector<pair<int,int>> news(fulen-1);
			for(int j = 0; j < fulen/2-1; j++){
				news[j].first = -(j+1)*2-sz(X);
				news[j].second = -(j+1)*2-sz(X)-1;
			}
			int digits = dig(fulen);
			vector<int> toadd(fulen);
			for(int j = 0; j < w; j++){
				toadd[j] = adj[i][j];
			}
			for(int j = 0; j < fulen; j++){
				int res = 0;
				for(int k = 0; k < digits; k++){
					res += (1<<k)*((j&(1<<(digits-k-1))) > 0);
				}
				if(res&1){
					news[res/2+fulen/2-1].second = toadd[j];
				}else{
					news[res/2+fulen/2-1].first = toadd[j];
				}
			}
			
			for(int j = 0; j < fulen-1; j++){
				X.push_back(news[j].first);
				Y.push_back(news[j].second);
			}
		}
	}
	answer(C,X,Y);
}

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