oj.uz

Submission #630422

# Submission time Handle Problem Language Result Execution time Memory
630422 2022-08-16T10:51:30 Z abeker Mechanical Doll (IOI18_doll) C++17
10 / 100
 8 ms 12644 KB 
#include <bits/stdc++.h>
#include "doll.h"
using namespace std;

const int MAXN = 1 << 19;
const int INF = 1e9;

int N;
bool state[2 * MAXN];
vector <int> a, c, x, y;
int which[2 * MAXN];
int ptr;

void output(vector <int> v) {
	for (auto it : v)
		printf("%d ", it);
	puts("");
}

void norm(vector <int> &v) {
	while (v.back() == INF)
		v.pop_back();
}

void add(int u, int v, int w) {
	x[u] = v;
	y[u] = w;
}

void build(int root, int x, int d) {
	if (!d)
		return;
	int lft = 2 * x;
	int rig = 2 * x + 1;
	if (d == 1) {
		lft += MAXN;
		rig += MAXN;
	}
	add(root + x, root + lft, root + rig);
	build(root, lft, d - 1);
	build(root, rig, d - 1);
}

void dfs(int node) {
	if (ptr >= N)
		return;
	state[node] ^= 1;
	if (x[node] == INF) {		
		which[node] = a[ptr++];
		dfs(0);
	}
	dfs(state[node] ? x[node] : y[node]);
}

void transform(int &ref) {
	if (ref == INF)
		return;
	if (which[ref] != -1)
		ref = which[ref];
	else
		ref = -(ref + 1);
}

void create_circuit(int M, vector <int> A) {
	memset(which, -1, sizeof which);
	
	a = A;
	a.push_back(0);
  N = a.size();
  vector <int> bits;
  for (int i = 17; i >= 0; i--)
  	if (N >> i & 1)
  		bits.push_back(i);
  
  c = vector <int> (M + 1, -1);
  x = y = vector <int> (2 * MAXN, INF);
  
  int sz = bits.size();
  int dep = bits[0] + 1;
  int curr = 0;
  for (int i = 0; i < sz; i++) {
  	int old = curr;
  	int steps = dep - bits[i] - i - 1;
  	if (i == sz - 1)
  		add(curr, 0, curr + 1);
 		while (steps--) {
 			curr++;
		 	add(curr, 0, curr + 1);
		}
		build(curr, 1, bits[i]);
		curr += 1 << bits[i];
		if (i < sz - 1)
			add(old, old + 1, curr);
  }
  
	dfs(0);
  
  norm(x);
	norm(y);
	
  for (int i = 0; i < x.size(); i++) {
  	transform(x[i]);
  	transform(y[i]);
	}
	
  answer(c, x, y);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:84:4: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   84 |    if (i == sz - 1)
      |    ^~
doll.cpp:86:4: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   86 |    while (steps--) {
      |    ^~~~~
doll.cpp:101:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |   for (int i = 0; i < x.size(); i++) {
      |                   ~~^~~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 12628 KB wrong motion
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 12628 KB wrong motion
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 12628 KB wrong motion
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

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

Subtask #5
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 12604 KB wrong motion
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 12604 KB wrong motion
2 Halted 0 ms 0 KB -