Submission #1225225

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225225		thelegendary08	Mechanical Doll (IOI18_doll)	C++20	37 / 100	265 ms	59768 KiB

doll

#include "doll.h"
#include<bits/stdc++.h>
#define vi vector<int>
#define vb vector<bool>
#define pb push_back
#define vvi vector<vector<int>>
#define f0r(i,n) for(int i = 0; i<n; i++)
#define vout(v) for(auto u : v)cout<<u<<' '; cout<<'\n';
using namespace std;
void create_circuit(int M, std::vector<int> A) {
	vi v;
	v.pb(0);
	for(auto u : A)v.pb(u);
	v.pb(0);
	vvi nxt(M+1);
	f0r(i, v.size() - 1){
		nxt[v[i]].pb(v[i+1]);
	}
	int curnum = 0;
	vi c(M+1);
	vi x;
	vi y;
	f0r(t, M+1){
		if(nxt[t].size() >= 2){
			int mx = ceil(log2(nxt[t].size()));
			int bts = (1 << mx) - nxt[t].size();
			int num = -1;
			int ptr = 0;
			c[t] = curnum - 1;
			
			f0r(i, mx){
				f0r(j, (1 << i)){
					if(i != mx - 1){
						x.pb(curnum + num * 2);
						y.pb(curnum + num * 2 - 1);
					}
					else{
						int ind1;
						int nind = j*2;
						ind1 = 0;
						for(int k = mx-1; k>=0; k--){
							ind1 += (1 << (mx -1- k)) * (((1 << k) & nind) > 0);
						}
						//cout<<nind<<' '<<ind1<<'\n';
						int nind2 = j*2 + 1;
						int ind2 = 0;
						for(int k = mx; k>=0; k--){
							ind2 += (1 << (mx -1- k)) * (((1 << k) & nind2) > 0);
						}
						//cout<<nind2<<' '<<ind2<<'\n';
						if(ind1 >= bts){
							x.pb(nxt[t][ind1 - bts]);
						}
						else{
							x.pb(curnum - 1);
						}
						if(ind2 >= bts){
							y.pb(nxt[t][ind2 - bts]);
						}
						else{
							y.pb(curnum - 1);
						}
					}
					
					num--;
				}
			}
			curnum += num + 1;
		}
		else if(nxt[t].size() == 1){
			c[t] = nxt[t][0];
		}
	}
	// vout(c);
	// vout(x);
	// vout(y);
	map<int,vi>fr;
	f0r(i,c.size()){
		fr[c[i]].pb(i);
	}
	f0r(i, x.size()){
		fr[x[i]].pb(i);
	}
	map<int,int> ne;
	map<int,int> nx;
	vb tk(x.size());
	for(int i = x.size(); i>=0; i--){
		if(x[i] == 0 && y[i] == 0){
			tk[i] = 1;
			nx[i] = x[i];
		}
	}
	int cnt = 0;
	f0r(i,x.size()){
		if(!tk[i]){
			ne[i] = cnt;
			cnt++;
		}
	}
	f0r(i, c.size()){
		if(c[i] < 0){
			if(tk[-c[i] - 1]){
				c[i] = nx[-c[i] - 1];
			}
			else{
				c[i] = -ne[-c[i] - 1] - 1;
			}
		}
	}
	
	vi xx; vi yy;
	f0r(i, x.size()){
		pair<int,int> p;
		if(!tk[i]){
			if(x[i] < 0){
				if(tk[-x[i] - 1]){
					p.first = nx[-x[i] - 1];
				}
				else{
					p.first = -ne[-x[i] - 1] - 1;
				}
			}
			else p.first = x[i];
			
			if(y[i] < 0){
				if(tk[-y[i] - 1]){
					p.second = nx[-y[i] - 1];
				}
				else{
					p.second = -ne[-y[i] - 1] - 1;
				}
			}
			else p.second = y[i];
		}
		xx.pb(p.first);
		yy.pb(p.second);	
	}
	// vout(c);
	// vout(xx);
	// vout(yy);
	answer(c,xx,yy);
	
}

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