Submission #793907

#	Time	Username	Problem	Language	Result	Execution time	Memory
793907		Sohsoh84	Mechanical Doll (IOI18_doll)	C++17	66.60 / 100	74 ms	10476 KiB

doll

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

using namespace std;

#define all(x)		(x).begin(), (x).end()
#define sep		' '
#define debug(x)	cerr << #x << ": " << x << endl;

const int MAXN = 1e6 + 10;

int s = 1, n, fake_vert;
vector<int> C, X, Y, A;

inline int create_switch(int x, int y) {
	X.push_back(x);
	Y.push_back(y);
	s++;
	return -(s - 1);
}

inline int create_trigger(int x) {
	X.push_back(-s);
	Y.push_back(x);
	
	s++;
	return -(s - 1); 
}

int build(int l = 0, int r = n - 1) {
	if (A[l] == fake_vert && A[r] == fake_vert) return fake_vert;
	if (l == r) return A[l];
	else {
		int mid = (l + r) >> 1;
		int a = build(l, mid);
		int b = build(mid + 1, r);

		//cerr << l << sep << r << sep << -s << sep << a << sep << b << endl;
		return create_switch(a, b);
	}
}

inline int f(int ind, int lg) {
	int ans = 0;
	while (lg--) {
		ans = (ans << 1 | (ind & 1));
		ind >>= 1;
	}

	return ans;
}

inline void print() {
	debug("print")
	for (int i = 0; i < int(C.size()); i++)
		cerr << i << ": " << C[i] << endl;

	cerr << endl;
	cerr << endl;

	for (int i = 0; i < int(X.size()); i++)
		cerr << -(i + 1) << ": " <<  X[i] << sep << Y[i] << endl;

	cerr << endl;
	cerr << endl;
}

void create_circuit(int m, vector<int> A_) {
	A = A_;
	A.push_back(0);
	A_.push_back(0);

	fake_vert = create_trigger(-1);	
	C.resize(m + 1);
	
	reverse(all(A));
	while (__builtin_popcount(int(A.size())) > 1) A.push_back(fake_vert);
	reverse(all(A));

	n = A.size();
	int lg = __builtin_ctz(n);

	vector<pair<int, int>> tmp;
	int ind = n - 1;
	while (ind >= 0 && A[ind] >= 0) {
		tmp.push_back({f(ind, lg), ind});
		ind--;
	}

	sort(all(tmp));	
	for (int i = 0; i < int(A_.size()); i++)
		A[tmp[i].second] = A_[i];

	int root = build(0, n - 1);
	Y[0] = root;

	while (A.back() < 0) A.pop_back();
	
	for (int i = 0; i <= m; i++) C[i] = root;

	assert(X.size() <= 2 * n);
//	print();
	answer(C, X, Y);
}

// TODO: change destincation of fake_vert to root

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from doll.cpp:2:
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:101:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  101 |  assert(X.size() <= 2 * n);
      |         ~~~~~~~~~^~~~~~~~

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