Submission #158011

#	Time	Username	Problem	Language	Result	Execution time	Memory
158011		kig9981	Mechanical Doll (IOI18_doll)	C++17	53 / 100	181 ms	22956 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;
	A.push_back(0);
	reverse(A.begin(),A.end());
	A.push_back(0);
	reverse(A.begin(),A.end());
	for(int 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);
		adj[i].resize(sz);
		for(k=osz;k<sz;k++) adj[i][k]=0x7fffffff;
		tree[i].resize(2*sz);
		reverse(adj[i].begin(),adj[i].end());
		for(int j=0;j<sz;j++) {
			k=0;
			for(int b=1;b<sz;b<<=1) {
				k<<=1;
				if(j&b) k|=1;
			}
			tree[i][sz+j]=adj[i][k];
		}
		for(int j=sz;--j;) if(tree[i][2*j]==0x7fffffff && tree[i][2*j+1]==0x7fffffff) tree[i][j]=0x7fffffff;
		for(int j=1;j<sz;j++) if(tree[i][j]!=0x7fffffff) {
			tree[i][j]=--c;
			X.push_back(0);
			Y.push_back(0);
		}
		for(int j=1;j<sz;j++) if(tree[i][j/2]!=0x7fffffff) {
			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: 0 / 10
• Subtask 5: 9.0000000036 / 18
• Subtask 6: 28.0000000112 / 56