oj.uz

Submission #1062228

# Submission time Handle Problem Language Result Execution time Memory
1062228 2024-08-16T22:20:22 Z Arapak Mechanical Doll (IOI18_doll) C++17
100 / 100
 88 ms 13576 KB 
// Author: Kajetan Ramsza
#include "bits/stdc++.h"
#include "doll.h"
using namespace std;

#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef long long ll;

#ifdef DEBUG
auto& operator<<(auto& os, pair<auto, auto> &p);
auto& operator<<(auto &os, const auto &v) 
  { os<<"{"; for(auto it=begin(v);it!=end(v);++it) {
    if(it != begin(v)) { os<<", "; } os<<(*it);
  } return os<<"}"; }
auto& operator<<(auto &os, pair<auto, auto> &p) 
  { return os<<"("<<p.first<<", "<<p.second<<")"; }

void dbg_out(auto... x) { ((cerr<<' '<<x), ...) << endl; }
#define dbg(x...) cerr<<"("<<#x<<"):", dbg_out(x)
#else
#define dbg(...)
#endif

int n, m, s;
vi a;
vi X, Y;
vi state;
int tim = 0;

int create_node(int a, int b) {
	X.push_back(a);
	Y.push_back(b);
	return sz(X);
}

int create_tree(int k, int depth) {
	dbg(k, depth);
	if(depth == 1) {
		if(k == 2) return create_node(-1, -1);
		if(k == 1) return create_node(0, -1);
		assert(false);
	}
	int p = 1<<(depth-1);
	if(k <= p) {
		int index = create_tree(k, depth-1);
		return create_node(0, index);
	}
	int a = create_tree(p, depth-1);
	int b = create_tree(k - p, depth-1);
	return create_node(a, b);
}

void simulate(int v) {
	dbg(v, tim);
	int &x = state[v-1] ? X[v-1] : Y[v-1];
	state[v-1] ^= 1;
	if(x == -1) x = -a[tim++];
	else simulate(x);
}

void create_circuit(int M, vi A) {
	dbg(m);
	a = A;
	a.push_back(0);
	n = a.size();
	m = M;
	int l = (int)ceil(log2(n));
	dbg(l);
	int root = create_tree(n, l);
	dbg(root);
	s = sz(X);
	rep(i,0,s)
		if(X[i] == 0) 
			X[i] = root;
	dbg(s, X, Y);
	state.assign(s, 1);
	rep(i,0,n) {
		dbg(i);
		simulate(root);
	}

	rep(i,0,s) {
		X[i] *= -1;
		Y[i] *= -1;
	}

	vi C(M + 1, -root);
	dbg(X, Y);
	answer(C, X, Y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 28 ms 5336 KB Output is correct
3 Correct 26 ms 5452 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 6 ms 1372 KB Output is correct
6 Correct 39 ms 7964 KB Output is correct
7 Correct 0 ms 344 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 28 ms 5336 KB Output is correct
3 Correct 26 ms 5452 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 6 ms 1372 KB Output is correct
6 Correct 39 ms 7964 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 57 ms 8812 KB Output is correct
9 Correct 57 ms 9588 KB Output is correct
10 Correct 88 ms 13576 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 28 ms 5336 KB Output is correct
3 Correct 26 ms 5452 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 6 ms 1372 KB Output is correct
6 Correct 39 ms 7964 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 57 ms 8812 KB Output is correct
9 Correct 57 ms 9588 KB Output is correct
10 Correct 88 ms 13576 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 78 ms 12692 KB Output is correct
15 Correct 51 ms 8304 KB Output is correct
16 Correct 82 ms 12552 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 80 ms 12952 KB Output is correct
21 Correct 0 ms 344 KB Output is correct
22 Correct 0 ms 348 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 49 ms 6992 KB Output is correct
3 Correct 48 ms 7084 KB Output is correct
4 Correct 76 ms 10804 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 49 ms 6992 KB Output is correct
3 Correct 48 ms 7084 KB Output is correct
4 Correct 76 ms 10804 KB Output is correct
5 Correct 78 ms 12308 KB Output is correct
6 Correct 82 ms 11780 KB Output is correct
7 Correct 76 ms 12060 KB Output is correct
8 Correct 77 ms 11528 KB Output is correct
9 Correct 46 ms 7024 KB Output is correct
10 Correct 76 ms 11568 KB Output is correct
11 Correct 74 ms 11060 KB Output is correct
12 Correct 53 ms 7292 KB Output is correct
13 Correct 51 ms 7792 KB Output is correct
14 Correct 55 ms 7792 KB Output is correct
15 Correct 57 ms 8048 KB Output is correct
16 Correct 2 ms 600 KB Output is correct
17 Correct 44 ms 7756 KB Output is correct
18 Correct 50 ms 7372 KB Output is correct
19 Correct 51 ms 7276 KB Output is correct
20 Correct 78 ms 11316 KB Output is correct
21 Correct 74 ms 11016 KB Output is correct
22 Correct 75 ms 11060 KB Output is correct