oj.uz

Submission #828885

# Submission time Handle Problem Language Result Execution time Memory
828885 2023-08-17T18:28:15 Z HamletPetrosyan Mechanical Doll (IOI18_doll) C++17
10 / 100
 21 ms 19128 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

#define len(a) ((int)(a).size())
#define pii pair<int, int>
#define fr first
#define sc second

int n, avl, logn;
vector<int> X, Y;
vector<pii> HRT;
int CNTR = -1, S = 0;

bool dfs(int v, int x, int y, int h){
	if(h >= logn - 1){
		HRT[y] = {v, x};
		HRT[y + (1 << (logn - 1))] = {v, x + 1};
		if(x + 1 < avl) return false;
		if(x < avl) X[-v - 1] = -1;
		S++;
		return true;
	}
	int rch = --CNTR;
	if(!dfs(rch, x + (1 << (logn - h - 1)), y + (1 << h), h + 1)) return false;
	Y[-v - 1] = rch;
	int lch = --CNTR;
	if(!dfs(lch, x, y, h + 1)){
		X[-v - 1] = -1;
		S++;
		return true;
	}
	X[-v - 1] = lch;
	S++;
	return true;
}

void create_circuit(int M, vector<int> A) {
	n = A.size();
	vector<int> C(M + 1);
	C[0] = A[0];
	for (int i = 1; i <= M; ++i) C[i] = -1;
	logn = ceil(log2(n));
	avl = (1 << logn) - n;

	X.resize(4 * n);
	Y.resize(4 * n);
	HRT.resize(4 * n);
	dfs(-1, 0, 0, 0);

	X.resize(S);
	Y.resize(S);

	if(n == 1){
		C[A[0]] = 0;
		answer(C, X, Y);
		return;
	}

	// cout << avl << "\n";

	int avlcnt = 0;
	for(int i = 0, v, x, ind; i < len(HRT); i++){
		// cout << "(" << HRT[i].fr << ", " << HRT[i].sc << ") ";
		v = -HRT[i].fr - 1;
		x = HRT[i].sc;
		if(x < avl){
			avlcnt++;
			continue;
		}
		ind = i - avlcnt + 1;
		if(x % 2) Y[v] = (ind == n) ? 0 : A[ind];
		else X[v] = (ind == n) ? 0 : A[ind]; 
	}

	// cout << endl;
	// for(auto h : C) cout << h << " ";
	// cout << endl << endl;
	// for(auto h : X) cout << h << " ";
	// cout << endl;
	// for(auto h : Y) cout << h << " ";
	// cout << endl;

	answer(C, X, Y);
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Runtime error 11 ms 10608 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Runtime error 11 ms 10608 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Runtime error 11 ms 10608 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

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

Subtask #5
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Runtime error 21 ms 19128 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Runtime error 21 ms 19128 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -