제출 #630422

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
630422		abeker	자동 인형 (IOI18_doll)	C++17	10 / 100	8 ms	12644 KiB

doll

#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);
}

컴파일 시 표준 에러 (stderr) 메시지

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
• Subtask 2: 0 / 4
• Subtask 3: 0 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 18
• Subtask 6: 0 / 56