Submission #303689

#	Time	Username	Problem	Language	Result	Execution time	Memory
303689		ryansee	Mechanical Doll (IOI18_doll)	C++14	47 / 100	249 ms	12644 KiB

doll

#include "doll.h"
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
void create_circuit(int M, std::vector<int> A) {
	int N = A.size();
	vector<vector<int> > qs(M + 1);
	for(int i = 0; i < N; ++i) {
		qs[A[i]].push_back(i);
	}
	bool subtask3 = true;
	for(int i = 1; i <= M; ++i) {
		if(qs[i].size() >= 5) {
			subtask3 = false;
		}
	}
	int bits = 1;
	while((1 << bits) < N) ++bits;
	vector<int> C(M + 1, -1);
	C[0] = A[0];
	vector<int> X((1 << bits) - 1, -1), Y((1 << bits) - 1, -1);
	for(int i = 1; i < 1 << (bits - 1); ++i) {
		X[i - 1] = -(2 * i);
		Y[i - 1] = -(2 * i + 1);
	}
	vector<int> perm;
	for(int i = 1 << bits; i < 2 << bits; ++i) {
		perm.push_back(i);
	}
	sort(perm.begin(), perm.end(), [&](int i, int j) {
		for(int k = 0; k < bits; ++k) {
			if(((i >> k) & 1) != ((j >> k) & 1)) {
				return ((i >> k) & 1) < ((j >> k) & 1);
			}
		}
		return false;
	});
	for(int i = 0; i < 1 << bits; ++i) {
		int tar = i - ((1 << bits) - N);
		if(tar < 0) tar = -1;
		else if(i != ((1 << bits) - 1)) tar = A[tar + 1];
		else tar = 0;
		if(perm[i] % 2 == 0) {
			X[perm[i] / 2 - 1] = tar;
		}
		else {
			Y[perm[i] / 2 - 1] = tar;
		}
	}
	// for(auto i:C) cerr<<i<<' '; cerr<<'\n';
	// for(auto i:X) cerr<<i<<' '; cerr<<'\n';
	// for(auto i:Y) cerr<<i<<' '; cerr<<'\n';
	answer(C, X, Y);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:12:7: warning: variable 'subtask3' set but not used [-Wunused-but-set-variable]
   12 |  bool subtask3 = true;
      |       ^~~~~~~~

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