Submission #384939

#	Time	Username	Problem	Language	Result	Execution time	Memory
384939		arman_ferdous	Mechanical Doll (IOI18_doll)	C++17	37 / 100	137 ms	11824 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

#define sz(v) (int)v.size()

const int M = (1 << 20);

int x[M], y[M], cnt[M], maxSwitch;

void build(int u, int L, int R) {
  maxSwitch = max(maxSwitch, u);
  cnt[u] = 0;

  if(L == R) return;
  int mid = L + R >> 1, lc = u << 1, rc = lc | 1;
  x[u] = lc, y[u] = rc;
  build(lc, L, mid); build(rc, mid + 1, R);
}

void insert(int u, int L, int R, int nxt) {
  if(L == R) {
    if(~cnt[u] & 1) x[u] = -nxt;
    else y[u] = -nxt;
    cnt[u] ^= 1;
    return;
  } int mid = L + R >> 1, lc = u << 1, rc = lc | 1;

  if(~cnt[u] & 1) {
    cnt[u] ^= 1;
    insert(lc, L, mid, nxt);
  }
  else {
    cnt[u] ^= 1;
    insert(rc, mid + 1, R, nxt);
  }
}


void create_circuit(int m, vector<int> a) {
  int n = a.size(); int initial = sz(a);

  while(n + 1 < 2 || __builtin_popcount(n + 1) != 1) {
    a.push_back(-1);
    n++;
  } a.push_back(0); n++;

  build(1, 1, n / 2);
  for(int i : a) insert(1, 1, n / 2, i);

  vector<int> C(m + 1, -1), X, Y;
  X.assign(x + 1, x + 1 + maxSwitch);
  Y.assign(y + 1, y + 1 + maxSwitch);

  for(int &i : X) i = -i;
  for(int &i : Y) i = -i;

  assert(sz(X) <= 2 * initial);

  answer(C, X, Y);
}

Compilation message (stderr)

doll.cpp: In function 'void build(int, int, int)':
doll.cpp:16:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   16 |   int mid = L + R >> 1, lc = u << 1, rc = lc | 1;
      |             ~~^~~
doll.cpp: In function 'void insert(int, int, int, int)':
doll.cpp:27:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |   } int mid = L + R >> 1, lc = u << 1, rc = lc | 1;
      |               ~~^~~

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