Submission #157941

#	Time	Username	Problem	Language	Result	Execution time	Memory
157941		kig9981	Mechanical Doll (IOI18_doll)	C++17	0 / 100	17 ms	14672 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>

using namespace std;

vector<int> adj[100001], tree[100001], num[100001];
bool m1[100001];

void create_circuit(int M, vector<int> A)
{
	int N=A.size()+1, c=0;
	vector<int> C(M+1), X, Y;
	A.push_back(0);
	for(int i=1;i<N;i++) adj[A[i-1]].push_back(A[i]);
	for(int i=1;i<=M;i++) {
		int sz=1, k, osz=adj[i].size();
		for(;sz<adj[i].size();sz<<=1);
		adj[i].resize(sz);
		m1[i]=osz<sz;
		for(k=osz;k<sz;k++) adj[i][k]=0x7fffffff;
		tree[i].resize(2*sz);
		for(int j=1;j<=osz;j++) swap(adj[i][sz-j],adj[i][osz-j]);
		for(int j=0;j<sz;j++) {
			k=0;
			for(int b=1;b<sz;b<<=1) {
				if(j&b) k|=1;
				k<<=1;
			}
			tree[i][sz+j]=adj[i][k];
		}
		for(int j=1;j<sz;j++) {
			tree[i][j]=--c;
			X.push_back(0);
			Y.push_back(0);
		}
		for(int j=sz;j<2*sz;j++) tree[i][j]=adj[i][j-sz];
		for(int j=1;i<sz;j++) {
			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];
	}
	C[0]=tree[A[0]][1];
	answer(C,X,Y);
}

Compilation message (stderr)

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

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