Submission #212250

#	Time	Username	Problem	Language	Result	Execution time	Memory
212250		MarcoMeijer	자동 인형 (IOI18_doll)	C++14	2 / 100	54 ms	11312 KiB

doll

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

//macros
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define INF 1e9
#define pb push_back
#define fi first
#define se second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n, s;
vi c, x, y, a, state;
vector<vi> nxt;

int LOG2(int x) {
  if(x <= 1) return 0;
  return 1+LOG2(x/2);
}
int createTriangle(int size) {
  if(size == 0) return 0;
  s++;
  int id=-s;
  x.pb(createTriangle(size-1));
  y.pb(createTriangle(size-1));
  state.pb(0);
  return id;
}
int setTriangle(int u, int value) {
  u = -1-u;
  if(state[u]) {
    if(y[u] == 0) y[u] = value;
    else setTriangle(y[u], value);
  } else {
    if(x[u] == 0) x[u] = value;
    else setTriangle(x[u], value);
  }
  state[u] = !state[u];
}

void create_circuit(int m, vi A) {
  a = A;
  s = 0;
  n = a.size();
  c.clear(); x.clear(); y.clear(); nxt.clear(); state.clear();
  c.resize(m+1);
  nxt.resize(m+1);

  nxt[0].pb(a[0]);
  RE(i,n) nxt[a[i]].pb(i==n-1 ? 0 : a[i+1]);

  RE(i,m+1) {
    int l2 = LOG2(nxt[i].size());
    c[i] = createTriangle(l2);
    if(nxt[i].size() == 1) c[i] = nxt[i][0];
    else if(nxt[i].size() != 0) {
      int empty = (1<<l2) - nxt[i].size();
      RE(j,empty) setTriangle(c[i],c[i]);
      RE(j,nxt[i].size()) setTriangle(c[i], nxt[i][j]);
    }
  }

  answer(c, x, y);
}

Compilation message (stderr)

doll.cpp: In function 'int setTriangle(int, int)':
doll.cpp:51:1: warning: no return statement in function returning non-void [-Wreturn-type]
   51 | }
      | ^

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