Submission #345689

#	Time	Username	Problem	Language	Result	Execution time	Memory
345689		wwdd	Mechanical Doll (IOI18_doll)	C++14	0 / 100	1 ms	204 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef pair<int,ii> ti;

int rev(int n, int nb) {
	int res = 0;
	for(int i=0;i<=nb;i++) {
		if(n&(1<<i)) {
			res |= 1<<(nb-i);
		}
	}
	return res;
}
void create_circuit(int M, std::vector<int> A) {
	int N = A.size();
	std::vector<int> C(M + 1);
	C[0] = -1;
	for (int i = 1; i <= M; ++i) {
		C[i] = -1;
	}
	/*
	std::vector<int> X(N), Y(N);
	for (int k = 0; k < N; ++k) {
		X[k] = Y[k] = A[k];
	}
	*/
	ll lb = 0;
	while((1<<lb) < N+1) {
		lb++;
	}
	vi X[2];
	X[0].assign(lb,-1);
	X[1].assign(lb,-1);
	for(int i=0;i<lb-1;i++) {
		X[0][i] = -(i+2);
	}
	vector<ti> mop;
	int SZ = N+1;
	for(int lev=1;lev<=lb;lev++) {
		int lz = lev;
		int num = 1<<(lb-lz);
		if(SZ >= num) {SZ -= num;
			int rs = X[0].size()-1;
			for(int j=0;j<num-1;j++) {
				X[0].push_back(-1);
				X[1].push_back(-1);
			}
			for(int j=num-1;j>1;j--) {
				X[(j&1)][(j>>1)+rs] = -(j+rs+1);
			}
			if(num > 1) {
				X[1][lev-1] = -(rs+2);
			} else {
				rs = lb-1;
			}
			if(lev == lb) {
				mop.push_back({0,{rs,0}});
				mop.push_back({(1<<(lz-1)),{rs,1}});
			} else {
				for(int j=0;j<num;j++) {
					mop.push_back({(rev(j,lb-lz-1)<<lz)|(1<<(lz-1)),{rs+(num>>1)+(j>>1),j&1}});
				}
			}
		}
	}
	sort(mop.begin(),mop.end());
	for(int i=0;i<mop.size();i++) {
		int sw = mop[i].second.first;
		int sid = mop[i].second.second;
		if(i < A.size()) {
			X[sid][sw] = A[i];
		}
	}
	ii fin = mop.back().second;
	X[fin.second][fin.first] = 0;
	for(int id=0;id<2;id++) {
		for(int i=0;i<X[id].size();i++) {
			cout << X[id][i] << " ";
		}
		cout << '\n';
	}
	answer(C, X[0], X[1]);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:71:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |  for(int i=0;i<mop.size();i++) {
      |              ~^~~~~~~~~~~
doll.cpp:74:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |   if(i < A.size()) {
      |      ~~^~~~~~~~~~
doll.cpp:81:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |   for(int i=0;i<X[id].size();i++) {
      |               ~^~~~~~~~~~~~~

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