Submission #440167

#	Time	Username	Problem	Language	Result	Execution time	Memory
440167		rainboy	Mechanical Doll (IOI18_doll)	C++11	78.40 / 100	103 ms	11372 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_++;
	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);
}

Compilation message (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:44:30: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   44 |   used[l] = (n + 1 & 1 << l_ - l) != 0;
      |                           ~~~^~~
doll.cpp:44:16: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
   44 |   used[l] = (n + 1 & 1 << l_ - l) != 0;
      |              ~~^~~
doll.cpp:47:39: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   47 |  for (i_ = 0, i = 0; i_ + 1 < 1 << l_ + 1; i_++) {
      |                                    ~~~^~~

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