oj.uz

Submission #219065

# Submission time Handle Problem Language Result Execution time Memory
219065 2020-04-03T15:32:35 Z mode149256 Mechanical Doll (IOI18_doll) C++14
100 / 100
 134 ms 15104 KB 
/*input

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

typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;

typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef vector<pi> vpi;
typedef vector<vpi> vpii;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
typedef vector<pd> vpd;
typedef vector<bool> vb;
typedef vector<vb> vbb;
typedef std::string str;
typedef std::vector<str> vs;

#define x first
#define y second
#define debug(...) cout<<"["<<#__VA_ARGS__<<": "<<__VA_ARGS__<<"]\n"

const int MOD = 1000000007;
const ll INF = std::numeric_limits<ll>::max();
const int MX = 100101;
const ld PI = 3.14159265358979323846264338327950288419716939937510582097494L;

template<typename T>
pair<T, T> operator+(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x + b.x, a.y + b.y); }
template<typename T>
pair<T, T> operator-(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x - b.x, a.y - b.y); }
template<typename T>
T operator*(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.x + a.y * b.y); }
template<typename T>
T operator^(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.y - a.y * b.x); }

template<typename T>
void print(vector<T> vec, string name = "") {
	cout << name;
	for (auto u : vec)
		cout << u << ' ';
	cout << '\n';
}

vi C;
vi X, Y;
int S = 0;

vii iseina;
int N;
int truksta;
int n;
int pradSw;
int maxLvl;
vpi place;

int nxtS() {
	X.push_back(0);
	Y.push_back(0);
	S++;
	// printf("s = %d, grazinu = %d\n", S, -S);
	return -S;
}

void make(int sw, int currLvl, int pos) {
	// int manoMedyElm = (1 << (maxLvl - currLvl + 1));
	// printf("sw = %d, pradsW = %d, manoMedyElm = %d, truksta = %d\n", sw, pradSw, manoMedyElm, truksta);
	// if (manoMedyElm <= truksta) {
	// 	X[sw] = Y[sw] = pradSw;
	// 	truksta -= manoMedyElm;
	// 	return;
	// }

	if (currLvl == maxLvl) {
		if (!truksta) place[pos] = {sw, 0};
		else {
			X[sw] = pradSw;
			truksta--;
		}

		pos |= (1 << currLvl);
		place[pos] = {sw, 1};
	} else {
		int ns;
		int manoMedyElm = (1 << (maxLvl - currLvl));
		// printf("sw = %d, pradsW = %d, manoMedyElm = %d, truksta = %d\n", sw, pradSw, manoMedyElm, truksta);
		if (manoMedyElm <= truksta) {
			X[sw] = pradSw;
			// X[sw] = Y[sw] = pradSw;
			truksta -= manoMedyElm;
		} else {
			ns = nxtS();
			X[sw] = ns;
			make(-X[sw], currLvl + 1, pos);
		}

		ns = nxtS();
		Y[sw] = ns;

		// print(X, "X: ");
		// print(Y, "Y: ");

		// printf("sw = %d, x y = %d %d, S = %d\n", sw, X[sw], Y[sw], S);
		make(-Y[sw], currLvl + 1, pos | (1 << currLvl));

		// printf("sz = %d, ~panaudojau = %d\n", manoMedyElm, S - pr);
	}
}

void daryk(int m) {
	int sz = (int)iseina[m].size();
	n =	(1 << (int)ceil(log2(sz)));
	maxLvl = log2(n);
	maxLvl--;
	truksta = n - sz;

	// printf("sz = %d, n = %d, mxlvl = %d,truksta = %d\n", sz, n, maxLvl, truksta);
	place = vpi(n, pi(MOD, MOD));

	int pr = S;

	int cs = nxtS();
	C[m] = cs;
	pradSw = C[m];

	make(-C[m], 0, 0);

	// printf("sz = %d, ~panaudojau = %d\n", sz, S - pr);

	// printf("m = %d, sz = %d, n = %d, place:\n", m, sz, n);
	// for (auto u : place)
	// 	printf("%d %d\n", u.x, u.y);
	// printf("\n");

	int j = 0;
	for (int i = 0; i < sz; ++i)
	{
		while (j < n and place[j].x == MOD) j++;
		assert(j < n);

		int h = place[j].x;

		// printf("i = %d, iseina = %d, h = %d\n", i, iseina[m][i], h);
		if (place[j].y) Y[h] = iseina[m][i];
		else X[h] = iseina[m][i];
		j++;
	}
}

void create_circuit(int M, vi A) {
	N = A.size();
	C = vi(M + 1);
	iseina = vii(M + 1);

	A.emplace_back(0);
	N++;

	for (int i = 0; i < N; ++i) {
		iseina[0].push_back(A[i]);
	}

	X.emplace_back(0);
	Y.emplace_back(0);

	daryk(0);

	for (int i = 1; i <= M; ++i)
		C[i] = pradSw;

	// C[iseina[0].back()] = 0;
	// for (int i = 1; i <= M; ++i)
	// {
	// 	if (iseina[i].empty()) C[i] = 0;
	// 	else if (iseina[i].size() == 1) C[i] = iseina[i][0];
	// 	else daryk(i);
	// }
	X.erase(X.begin());
	Y.erase(Y.begin());

	// printf("S = %d\n", S);
	// print(C, "C: ");
	// for (int i = 0; i < S; ++i) printf("%d ", X[i]); printf("\n");
	// for (int i = 0; i < S; ++i) printf("%d ", Y[i]); printf("\n");
	answer(C, X, Y);
}

Compilation message

doll.cpp: In function 'void daryk(int)':
doll.cpp:132:6: warning: unused variable 'pr' [-Wunused-variable]
  132 |  int pr = S;
      |      ^~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 38 ms 7820 KB Output is correct
3 Correct 35 ms 6936 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 18 ms 3788 KB Output is correct
6 Correct 51 ms 9624 KB Output is correct
7 Correct 1 ms 204 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 38 ms 7820 KB Output is correct
3 Correct 35 ms 6936 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 18 ms 3788 KB Output is correct
6 Correct 51 ms 9624 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 62 ms 10640 KB Output is correct
9 Correct 65 ms 11920 KB Output is correct
10 Correct 91 ms 15104 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 38 ms 7820 KB Output is correct
3 Correct 35 ms 6936 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 18 ms 3788 KB Output is correct
6 Correct 51 ms 9624 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 62 ms 10640 KB Output is correct
9 Correct 65 ms 11920 KB Output is correct
10 Correct 91 ms 15104 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 91 ms 13724 KB Output is correct
15 Correct 71 ms 9324 KB Output is correct
16 Correct 134 ms 13092 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 130 ms 14348 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 2 ms 204 KB Output is correct
6 Correct 2 ms 204 KB Output is correct
7 Correct 2 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 50 ms 7620 KB Output is correct
3 Correct 50 ms 7660 KB Output is correct
4 Correct 78 ms 10516 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 50 ms 7620 KB Output is correct
3 Correct 50 ms 7660 KB Output is correct
4 Correct 78 ms 10516 KB Output is correct
5 Correct 81 ms 12696 KB Output is correct
6 Correct 88 ms 12052 KB Output is correct
7 Correct 112 ms 12232 KB Output is correct
8 Correct 81 ms 11556 KB Output is correct
9 Correct 51 ms 7656 KB Output is correct
10 Correct 76 ms 11392 KB Output is correct
11 Correct 79 ms 10844 KB Output is correct
12 Correct 52 ms 7892 KB Output is correct
13 Correct 59 ms 8604 KB Output is correct
14 Correct 65 ms 8804 KB Output is correct
15 Correct 55 ms 9128 KB Output is correct
16 Correct 2 ms 512 KB Output is correct
17 Correct 50 ms 7576 KB Output is correct
18 Correct 49 ms 7780 KB Output is correct
19 Correct 77 ms 7872 KB Output is correct
20 Correct 77 ms 11088 KB Output is correct
21 Correct 76 ms 10800 KB Output is correct
22 Correct 82 ms 10892 KB Output is correct