Submission #838077

#	Time	Username	Problem	Language	Result	Execution time	Memory
838077		tolbi	Mechanical Doll (IOI18_doll)	C++17	100 / 100	112 ms	14932 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
#define coutarr(x) for(auto &it : x) cout<<it<<" ";cout<<endl;
#define tol(bi) (1LL<<((long long)(bi)))
void create_circuit(int M, vector<int> A) {
	int n = A.size();
	vector<int> X(tol(ceil(log2(n+1)))-1);
	vector<int> Y(X.size());
	int S = X.size();
	int cnt = n+1;
	for (int i = S-1; i >= 0; i--){
		X[i]=(i+1)*2;
		Y[i]=(i+1)*2+1;
		if (Y[i]>S){
			if (cnt) Y[i]=n+1-(cnt--);
			else Y[i]=-1;
		}
		else Y[i]=-Y[i];
		if (X[i]>S){
			if (cnt) X[i]=n+1-(cnt--);
			else X[i]=-1;
		}
		else X[i]=-X[i];
	}
	vector<bool> gerekli(S,false);
	for (int i = S-1; i >= 0; i--){
		if (X[i]>=0 || Y[i]>=0 || (X[i]<0 && Y[i]<0 && (gerekli[(-X[i])-1] || gerekli[(-Y[i])-1]))) gerekli[i]=true;
	}
	cnt=1;
	vector<int> gercek(S,-1);
	vector<int> x;
	vector<int> y;
	for (int i = 0; i < S; ++i)
	{
		if (gerekli[i]){
			gercek[i]=cnt++;
		}
	}
	for (int i = 0; i < S; i++){
		if (!gerekli[i]) continue;
		if (X[i]>=-1){
			x.push_back(X[i]);
			y.push_back(Y[i]);
			continue;
		}
		int xv = gercek[(-X[i])-1];
		int yv = gercek[(-Y[i])-1];
		if (xv!=-1) xv=-xv;
		if (yv!=-1) yv=-yv;
		x.push_back(xv);
		y.push_back(yv);
	}
	vector<int> C(M+1,-1);
	vector<int> gez;
	int node = -1;
	vector<int> state(S,0);
	while (gez.size()<n){
		if (node>=0){
			gez.push_back(node);
			node=-1;
		}
		else {
			node=-node-1;
			if (state[node]==0) state[node]=1;
			else state[node]=0;
			if (state[node]==1){
				node=x[node];
			}
			else node=y[node];
		}
	}
	vector<int> val(n+1);
	for (int i = 0; i < n; ++i)
	{
		val[gez[i]]=A[i];
	}
	for (int i = 0; i < S; i++){
		if (x[i]>0) x[i]=val[x[i]];
		if (y[i]>0) y[i]=val[y[i]];
	}
	answer(C,x,y);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:58:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   58 |  while (gez.size()<n){
      |         ~~~~~~~~~~^~

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