Submission #158032

#	Time	Username	Problem	Language	Result	Execution time	Memory
158032		kig9981	Mechanical Doll (IOI18_doll)	C++17	85.55 / 100	133 ms	20352 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
 
using namespace std;
 
vector<int> adj[100001], tree[100001], num[100001];

void create_circuit(int M, vector<int> A)
{
	int N=A.size()+2, c=0;
	vector<int> C(M+1), X, Y, temp;
	A.push_back(0);
	reverse(A.begin(),A.end());
	A.push_back(0);
	reverse(A.begin(),A.end());
	for(int i=1;i<N;i++) adj[A[i-1]].push_back(A[i]);
	for(int i=0;i<=M;i++) if(adj[i].size()) {
		int sz=1, k, osz=adj[i].size();
		for(;sz<adj[i].size();sz<<=1);
		tree[i].resize(2*sz,-1);
		for(int j=0;j<sz;j++) tree[i][sz+j]=0x7fffffff;
		temp.clear();
		for(int j=0;j<osz;j++) {
			k=0;
			for(int b=1;b<sz;b<<=1) {
				k<<=1;
				if((sz-1-j)&b) k|=1;
			}
			temp.push_back(k);
		}
		sort(temp.begin(),temp.end());
		for(int j=0;j<osz;j++) {
			k=0;
			for(int b=1;b<sz;b<<=1) {
				k<<=1;
				if(temp[j]&b) k|=1;
			}
			tree[i][sz+k]=adj[i][j];
		}
		for(int j=sz;--j;) if(tree[i][2*j]==tree[i][2*j+1] && tree[i][2*j]>0) {
			tree[i][j]=tree[i][2*j];
			tree[i][2*j]=tree[i][2*j+1]=0x7fffffff;
		}
		for(int j=1;j<sz;j++) if(tree[i][j]<0) {
			tree[i][j]=--c;
			X.push_back(0);
			Y.push_back(0);
		}
		for(int j=1;j<sz;j++) if(tree[i][j]<0) {
			X[-tree[i][j]-1]=tree[i][2*j]==0x7fffffff ? tree[i][1]:tree[i][2*j];
			Y[-tree[i][j]-1]=tree[i][2*j+1]==0x7fffffff ? tree[i][1]:tree[i][2*j+1];
		}
		adj[i].clear();
		C[i]=tree[i][1];
	}
	answer(C,X,Y);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:19:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |   for(;sz<adj[i].size();sz<<=1);
      |        ~~^~~~~~~~~~~~~~

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