Submission #793816

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
793816	2023-07-26T07:00:28 Z	NothingXD	Mechanical Doll (IOI18_doll)	C++17	16 / 100	89 ms	19564 KB

doll

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

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef double ld;
typedef complex<ld> point;

void debug_out(){cerr << endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cerr << H << ' ';
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 2e5 + 10;

int n, m, a[maxn], out[maxn], out1[maxn], out2[maxn], res;
vector<int> idx[maxn];

void solve(int v, int root, vector<int> tmp){
	//debug(v);
	//for (auto x: tmp) debug(x);
	vector<int> l;
	vector<int> r;
	for (int i = 0; i < tmp.size(); i++){
		if (i&1) r.push_back(tmp[i]);
		else l.push_back(tmp[i]);
	}
	if (l.back() == -1){
		out1[v-1] = -root;
	}
	else if (l.size() == 1){
		out1[v-1] = a[l[0]+1];
	}
	else{
		res++;
		out1[v-1] = -res;
		solve(res, root, l);
	}
	if (r.back() == -1){
		out2[v-1] = -root;
	}
	else if (r.size() == 1){
		out2[v-1] = a[r[0]+1];
	}
	else{
		res++;
		out2[v-1] = -res;
		solve(res, root, r);
	}
}

void create_circuit(int M, vector<int> A) {
	n = A.size(); m = M;
	for (int i = 0; i < n; i++){
		a[i] = A[i];
		idx[a[i]].push_back(i);
	}
	a[n] = 0;
	out[0] = a[0];
	for (int i = 1; i <= m; i++){
		int tmp = idx[i].size();
		if (tmp == 0){
			out[i] = 0;
			continue;
		
		}
		reverse(all(idx[i]));
		while(tmp % 2 == 0) tmp /= 2;
		while(tmp != 1){
			idx[i].push_back(-1);
			tmp = idx[i].size();
			while(tmp % 2 == 0) tmp /= 2;
		}
		reverse(all(idx[i]));
		int sz = idx[i].size();
		if (sz == 1){
			out[i] = a[idx[i][0]+1];
			continue;
		}
	//	debug(i, idx[i].size());
		res++;
		out[i] = -res;
		solve(res, res, idx[i]);
	}
	vector<int> C(m+1), X(res), Y(res);
	for (int i = 0; i <= m; i++){
		C[i] = out[i];
	//	debug(i, C[i]);
	}
	//debug(res);
	for (int i = 0; i < res; i++){
		X[i] = out1[i];
		Y[i] = out2[i];
	//	debug(-(i+1), X[i], Y[i]);
	}
	answer(C, X, Y);
}

Compilation message

doll.cpp: In function 'void solve(int, int, std::vector<int>)':
doll.cpp:35:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |  for (int i = 0; i < tmp.size(); i++){
      |                  ~~^~~~~~~~~~~~

Subtask #1
2.0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	4948 KB	Output is correct
2	Correct	22 ms	9372 KB	Output is correct
3	Correct	16 ms	8788 KB	Output is correct
4	Correct	2 ms	4948 KB	Output is correct
5	Correct	9 ms	6484 KB	Output is correct
6	Correct	25 ms	10816 KB	Output is correct
7	Correct	2 ms	4948 KB	Output is correct

Subtask #2
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	4948 KB	Output is correct
2	Correct	22 ms	9372 KB	Output is correct
3	Correct	16 ms	8788 KB	Output is correct
4	Correct	2 ms	4948 KB	Output is correct
5	Correct	9 ms	6484 KB	Output is correct
6	Correct	25 ms	10816 KB	Output is correct
7	Correct	2 ms	4948 KB	Output is correct
8	Correct	36 ms	11736 KB	Output is correct
9	Correct	38 ms	12152 KB	Output is correct
10	Correct	57 ms	15064 KB	Output is correct
11	Correct	2 ms	4988 KB	Output is correct
12	Correct	2 ms	4948 KB	Output is correct
13	Correct	2 ms	4948 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	4948 KB	Output is correct
2	Correct	22 ms	9372 KB	Output is correct
3	Correct	16 ms	8788 KB	Output is correct
4	Correct	2 ms	4948 KB	Output is correct
5	Correct	9 ms	6484 KB	Output is correct
6	Correct	25 ms	10816 KB	Output is correct
7	Correct	2 ms	4948 KB	Output is correct
8	Correct	36 ms	11736 KB	Output is correct
9	Correct	38 ms	12152 KB	Output is correct
10	Correct	57 ms	15064 KB	Output is correct
11	Correct	2 ms	4988 KB	Output is correct
12	Correct	2 ms	4948 KB	Output is correct
13	Correct	2 ms	4948 KB	Output is correct
14	Correct	77 ms	16676 KB	Output is correct
15	Correct	45 ms	12032 KB	Output is correct
16	Correct	63 ms	15828 KB	Output is correct
17	Correct	2 ms	4948 KB	Output is correct
18	Correct	3 ms	5008 KB	Output is correct
19	Correct	2 ms	4948 KB	Output is correct
20	Correct	74 ms	17264 KB	Output is correct
21	Correct	3 ms	5008 KB	Output is correct
22	Correct	2 ms	4948 KB	Output is correct