Submission #788803

#	Time	Username	Problem	Language	Result	Execution time	Memory
788803		ToniB	Mechanical Doll (IOI18_doll)	C++17	37 / 100	104 ms	16340 KiB

doll

#include <bits/stdc++.h>
#include "doll.h"
using namespace std;
const int MAXN = 400000;

int n, m, cur = 1, s, x[MAXN], y[MAXN];
vector<int> a;
vector<int> c, x_ans, y_ans;

void dfs(int node, vector<int> v){
	cur = max(cur, node);
	if(v.size() == 2){
		x[node - 1] = v[0];
		y[node - 1] = v[1];
		return ;
	}
	x[node - 1] = -node * 2;
	y[node - 1] = -(node * 2 + 1);
	vector<int> L, R;
	for(int i = 0; i < (int)v.size(); ++i){
		if(i & 1) R.push_back(v[i]);
		else L.push_back(v[i]);
	}
	dfs(node * 2, L);
	dfs(node * 2 + 1, R);
}

void create_circuit(int _m, vector<int> _a){
	m = _m; a = _a; n = a.size();
	for(int i = 0; i <= m; ++i) c.push_back(-1);
	int p = 1;
	while(p < n + 1){
		p *= 2;
	}
	for(int i = n + 1; i < p; ++i) a.push_back(-1);
	a.push_back(0);
	dfs(1, a);
	x_ans.resize(cur); y_ans.resize(cur);
	for(int i = 0; i < cur; ++i){
		x_ans[i] = x[i];
		y_ans[i] = y[i];
	}
	assert(x_ans.size() <= 2 * n);
	answer(c, x_ans, y_ans);
}

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:1:
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:43:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   43 |  assert(x_ans.size() <= 2 * n);
      |         ~~~~~~~~~~~~~^~~~~~~~

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