Submission #1072492

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1072492	2024-08-23T20:16:43 Z	pawned	Mechanical Doll (IOI18_doll)	C++17	2 / 100	35 ms	8668 KB

doll

#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;

#include "doll.h"

int calc(int x) {	// depth needed
	int curr = 1;
	int res = 0;
	while (curr < x) {
		curr *= 2;
		res++;
	}
	return res - 1;
}

vi calcOrder(int d) {
	vi order = {0};
	for (int j = 0; j <= d; j++) {
		vi order2;
		for (int x : order) {
			order2.pb(x);
			order2.pb(x + (1 << j));
		}
		order = order2;
	}
	return order;
}

void create_circuit(int M, vi A) {
	int N = A.size();
/*	cout<<"A: ";
	for (int i = 0; i < N; i++) {
		cout<<A[i]<<" ";
	}
	cout<<endl;*/
	vi allr[M + 1];
	allr[0].pb(A[0]);
	for (int i = 0; i < N - 1; i++) {
		allr[A[i]].pb(A[i + 1]);
	}
/*	cout<<"allr: "<<endl;
	for (int i = 0; i < M; i++) {
		cout<<i<<": ";
		for (int x : allr[i])
			cout<<x<<" ";
		cout<<endl;
	}*/
	int curr = -1;	// current id
	vi ans(M + 1, 0);
	vector<ii> rit;	// negative to negative
	// create binary tree
	for (int i = 0; i <= M; i++) {
		int K = allr[i].size();
		if (K == 0) {	// never used
			ans[i] = 0;
			continue;
		}
		if (K == 1) {
			ans[i] = allr[i][0];
			continue;
		}
		ans[i] = curr;	// go to binary tree
		int depth = calc(K);
		vi order = calcOrder(depth);
		// order[i]: time that cell i is used
/*		cout<<"order: ";
		for (int x : order)
			cout<<x<<" ";
		cout<<endl;*/
		vi conv((1 << (depth + 1)), -1);
		// conv[i]: cell used at time i
		for (int j = 0; j < (1 << (depth + 1)); j++) {
			conv[order[j]] = j;
		}
		for (int j = 0; j < (1 << depth) - 1; j++) {
			rit.pb({curr - (2 * j + 1), curr - (2 * j + 2)});
		}
		for (int j = (1 << depth) - 1; j < (1 << (depth + 1)) - 1; j++) {
			int pos = j - ((1 << depth) - 1);
			ii tp = {0, 0};
			if (order[2 * pos] < K)
				tp.fi = allr[i][order[2 * pos]];
			if (order[2 * pos + 1] < K)
				tp.se = allr[i][order[2 * pos + 1]];
			rit.pb(tp);
		}
		curr -= ((1 << (depth + 1)) - 1);
	}
	vi ans1, ans2;
	for (ii p : rit) {
		ans1.pb(p.fi);
		ans2.pb(p.se);
	}
	answer(ans, ans1, ans2);
}

Subtask #1
2.0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	18 ms	6980 KB	Output is correct
3	Correct	14 ms	5724 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	7 ms	3932 KB	Output is correct
6	Correct	24 ms	8428 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct

Subtask #2
0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	18 ms	6980 KB	Output is correct
3	Correct	14 ms	5724 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	7 ms	3932 KB	Output is correct
6	Correct	24 ms	8428 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Incorrect	35 ms	8668 KB	wrong motion
9	Halted	0 ms	0 KB	-

Subtask #3
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	18 ms	6980 KB	Output is correct
3	Correct	14 ms	5724 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	7 ms	3932 KB	Output is correct
6	Correct	24 ms	8428 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Incorrect	35 ms	8668 KB	wrong motion
9	Halted	0 ms	0 KB	-