oj.uz

Submission #793901

# Submission time Handle Problem Language Result Execution time Memory
793901 2023-07-26T07:56:20 Z Sohsoh84 Mechanical Doll (IOI18_doll) C++17
66.5995 / 100
 84 ms 10840 KB 
#include "doll.h"
#include <bits/stdc++.h>

using namespace std;

#define all(x)		(x).begin(), (x).end()
#define sep		' '
#define debug(x)	cerr << #x << ": " << x << endl;

const int MAXN = 1e6 + 10;

int s = 1, n, fake_vert;
vector<int> C, X, Y, A;

inline int create_switch(int x, int y) {
	X.push_back(x);
	Y.push_back(y);
	s++;
	return -(s - 1);
}

inline int create_trigger(int x) {
	X.push_back(-s);
	Y.push_back(x);
	
	s++;
	return -(s - 1); 
}

int build(int l = 0, int r = n - 1) {
	if (A[l] == fake_vert && A[r] == fake_vert) return fake_vert;
	if (l == r) return A[l];
	else {
		int mid = (l + r) >> 1;
		int a = build(l, mid);
		int b = build(mid + 1, r);

		//cerr << l << sep << r << sep << -s << sep << a << sep << b << endl;
		return create_switch(a, b);
	}
}

inline int f(int ind, int lg) {
	int ans = 0;
	while (lg--) {
		ans = (ans << 1 | (ind & 1));
		ind >>= 1;
	}

	return ans;
}

inline void print() {
	debug("print")
	for (int i = 0; i < int(C.size()); i++)
		cerr << i << ": " << C[i] << endl;

	cerr << endl;
	cerr << endl;

	for (int i = 0; i < int(X.size()); i++)
		cerr << -(i + 1) << ": " <<  X[i] << sep << Y[i] << endl;

	cerr << endl;
	cerr << endl;
}

void create_circuit(int m, vector<int> A_) {
	A = A_;
	A.push_back(0);
	A_.push_back(0);

	fake_vert = create_trigger(-1);	
	C.resize(m + 1);
	
	reverse(all(A));
	while (__builtin_popcount(int(A.size())) > 1) A.push_back(fake_vert);
	reverse(all(A));

	n = A.size();
	int lg = __builtin_ctz(n);

	vector<pair<int, int>> tmp;
	int ind = n - 1;
	while (ind >= 0 && A[ind] >= 0) {
		tmp.push_back({f(ind, lg), ind});
		ind--;
	}

	sort(all(tmp));	
	for (int i = 0; i < int(A_.size()); i++)
		A[tmp[i].second] = A_[i];

	int root = build(0, n - 1);
	Y[0] = root;

	while (A.back() < 0) A.pop_back();
	
	for (int i = 0; i <= m; i++) C[i] = root;

//	print();
	answer(C, X, Y);
}

// TODO: change destincation of fake_vert to root

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 28 ms 5916 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 28 ms 5916 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 28 ms 5916 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
16.1998901226 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Partially correct 39 ms 7104 KB Output is partially correct
3 Correct 42 ms 7112 KB Output is correct
4 Correct 70 ms 10100 KB Output is correct

Subtask #6
50.3996581592 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Partially correct 39 ms 7104 KB Output is partially correct
3 Correct 42 ms 7112 KB Output is correct
4 Correct 70 ms 10100 KB Output is correct
5 Correct 74 ms 10840 KB Output is correct
6 Correct 72 ms 10580 KB Output is correct
7 Correct 70 ms 10716 KB Output is correct
8 Correct 67 ms 10368 KB Output is correct
9 Correct 46 ms 7104 KB Output is correct
10 Correct 84 ms 10240 KB Output is correct
11 Correct 72 ms 10104 KB Output is correct
12 Correct 40 ms 7104 KB Output is correct
13 Partially correct 48 ms 7424 KB Output is partially correct
14 Correct 48 ms 7424 KB Output is correct
15 Correct 49 ms 7540 KB Output is correct
16 Correct 2 ms 564 KB Output is correct
17 Correct 45 ms 6668 KB Output is correct
18 Partially correct 51 ms 7188 KB Output is partially correct
19 Correct 44 ms 7184 KB Output is correct
20 Correct 66 ms 10244 KB Output is correct
21 Correct 67 ms 10116 KB Output is correct
22 Correct 67 ms 10060 KB Output is correct