Submission #1199230

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199230		Gr1sen	Mechanical Doll (IOI18_doll)	C++20	Compilation error	0 ms	0 KiB

doll

#include "doll.h"
#include<algorithm>
#include<iostream>
#include<vector>
#include<iomanip>
#include<unordered_map>

using namespace std;

#define vi vector<int>
#define vvi vector<vi>

void print(vi &L) {
	cerr << "{";
	for (auto i : L) cerr << i << ", ";
	cerr << "}" << endl;
}

vi X, Y;

int oi(int a) {
	return -a-1;
}

int oink(int s, int k, int d) {
	//cerr << "oink(" << s << ", " << k << ", " << d << ")" << endl;
	int p = X.size();
	if (k <= 0) return s;
	if (d <= 1) {
		if (k == 1) return 0;
		X.push_back(0);
		Y.push_back(0);
		return oi(p);
	}
	X.push_back(0);
	Y.push_back(0);
	int a = pow(2, (int)log2(k));
	if (a >= k) a /= 2;
	//cerr << "a : " << a << endl;
	Y[p] = oink(s, a, d-1);
	X[p] = oink(s, k-a, d-1);
	return oi(p);
}

void oinkoink(vi &L, vi &K, int p, int pl, int s) {
	/*
	cerr << "oinkoink(..." << p << ", " << pl << ", " << s << ")" << endl;
	print(L);
	print(K);
	print(X);
	print(Y);
	//*/
	if (pl >= L.size()) return;
	if (K[oi(p)]) {
		K[oi(p)] = 0;
		if (Y[oi(p)] == 0) {
			Y[oi(p)] = L[pl];
			oinkoink(L, K, s, pl+1, s);
			return;
		}
		oinkoink(L, K, Y[oi(p)], pl, s);
		return;
	}
	K[oi(p)] = 1;
	if (X[oi(p)] == 0) {
		X[oi(p)] = L[pl];
		oinkoink(L, K, s, pl+1, s);
		return;
	}
	oinkoink(L, K, X[oi(p)], pl, s);
}

void create_circuit(int m, vector<int> A) {
	int n = A.size();
	A.push_back(0);
	vi C(m + 1, 0);
	X.clear(); Y.clear();
	vvi L(m+1);
	L[0] = {A[0]};
	for (int i = 0; i < n; i++) {
		L[A[i]].push_back(A[i+1]);
	}
	int l = 0;
	for (int i = 0; i < m+1; i++) {
		/*
		cerr << "iteration : " << i << endl;
		cerr << "C : ";
		print(C);
		cerr << "X : ";
		print(X);
		cerr << "Y : ";
		print(Y);
		//*/
		if (L[i].size() == 0) continue;
		if (L[i].size() == 1) {
			C[i] = L[i][0];
			continue;
		}
		int a = (int)log2(L[i].size());
		int b = pow(2, a);
		if (b == L[i].size()) {
			b /= 2;
			a--;
		}
		X.push_back(-1);
		Y.push_back(-1);
		int p = X.size()-1;
		C[i] = oi(p);
		X[p] = oink(oi(p), L[i].size()-b, a+1);
		Y[p] = oink(oi(p), b, a+1);
		vi K(X.size(), 0);
		oinkoink(L[i], K, oi(p), 0, oi(p));
	}
	/*
	cerr << "C : ";
	print(C);
	cerr << "X : ";
	print(X);
	cerr << "Y : ";
	print(Y);
	//*/
	answer(C, X, Y);
}

Compilation message (stderr)

doll.cpp: In function 'int oink(int, int, int)':
doll.cpp:37:29: error: 'log2' was not declared in this scope
   37 |         int a = pow(2, (int)log2(k));
      |                             ^~~~
doll.cpp:37:17: error: 'pow' was not declared in this scope
   37 |         int a = pow(2, (int)log2(k));
      |                 ^~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:99:30: error: 'log2' was not declared in this scope
   99 |                 int a = (int)log2(L[i].size());
      |                              ^~~~
doll.cpp:100:25: error: 'pow' was not declared in this scope
  100 |                 int b = pow(2, a);
      |                         ^~~