제출 #440171

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
440171		rainboy	자동 인형 (IOI18_doll)	C++11	100 / 100	91 ms	12100 KiB

doll

#include "doll.h"
#include <string.h>

using namespace std;

typedef vector<int> vi;

const int N = 200000, M = 100000, L = 17, N_ = 1 << L;	/* L = floor(log2(N))) */

int tmp[N_];

void split(int *aa, int n) {
	int i, j, k;

	for (i = 0, j = n / 2, k = 0; k < n; k++)
		tmp[k % 2 == 0 ? i++ : j++] = aa[k];
	memcpy(aa, tmp, n * sizeof *tmp);
}

vi xx(N * 2), yy(N * 2); int k;

int build(int *aa, int n) {
	if (n == 1)
		return aa[0];
	else {
		int u = k++;

		split(aa, n);
		xx[u] = build(aa, n / 2), yy[u] = build(aa + n / 2, n / 2);
		return -(u + 1);
	}
}

char used[L + 1]; int aaa[L + 1][N + 1], nn[L + 1];

void create_circuit(int m, vi aa) {
	vi cc(m + 1, -1);
	int n = aa.size(), l_, l, i, i_;

	l_ = 1;
	while (1 << l_ + 1 <= n + 1)
		l_++;
	if (1 << l_ == n + 1) {
		for (i = 0; i <= n; i++)
			aaa[0][i] = i == n ? 0 : aa[i];
		build(aaa[0], n + 1);
	} else {
		for (l = 0; l <= l_; l++)
			used[l] = (n + 1 & 1 << l_ - l) != 0;
		for (l = 0; l <= l_; l++)
			yy[l] = l == l_ ? 0 : -(l + 1 + 1);
		for (i_ = 0, i = 0; i_ + 1 < 1 << l_ + 1; i_++) {
			l = 0;
			while (((i_ + 1) & 1 << l) == 0)
				l++;
			if (used[l])
				aaa[l][nn[l]++] = i == n ? -1 : aa[i++];
		}
		k = l_ + 1;
		for (l = 0; l <= l_; l++)
			xx[l] = used[l] ? build(aaa[l], nn[l]) : -1;
	}
	xx.resize(k), yy.resize(k);
	answer(cc, xx, yy);
}

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

doll.cpp: In function 'void create_circuit(int, vi)':
doll.cpp:41:17: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   41 |  while (1 << l_ + 1 <= n + 1)
      |              ~~~^~~
doll.cpp:49:31: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   49 |    used[l] = (n + 1 & 1 << l_ - l) != 0;
      |                            ~~~^~~
doll.cpp:49:17: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
   49 |    used[l] = (n + 1 & 1 << l_ - l) != 0;
      |               ~~^~~
doll.cpp:52:40: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   52 |   for (i_ = 0, i = 0; i_ + 1 < 1 << l_ + 1; i_++) {
      |                                     ~~~^~~

• Subtask 1: 2 / 2
• Subtask 2: 4 / 4
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 18 / 18
• Subtask 6: 56 / 56