제출 #1222459

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1222459		zaki98	자동 인형 (IOI18_doll)	C++20	70.67 / 100	77 ms	12580 KiB

doll

#include <bits/stdc++.h>
#include "doll.h"
using namespace std;
#define LOO(i,a,b) for (int i = a; i <=b;i++)
#define pii pair<int,int>
#define PB push_back
#define F first
typedef long long ll;
void answer(std::vector<int> C, std::vector<int> X, std::vector<int> Y);
int curr = 0;
int getbigg(int n) {
  int num = 1 << (31 - __builtin_clz(n));
  if (num==n) return n;
  return 1 << (32 - __builtin_clz(n));
}
vector<pii> outgoers;
bool build(int v, int l, int r, int m, int rii) {
  if (l==r) {
     if (r==rii||r<m) {
       return true;
     }
      return false;
  }
  int mid = (l+r)/2;
  pii mhm = {-1,-1};
  if (build(2*v, l, mid, m, rii)) {
    mhm.F = curr;
  }
  if (build(2*v+1, mid+1,r,m,rii)) {
    mhm.second = curr;
  }
  if (mhm!=make_pair(-1,-1)) {
    curr++;
    outgoers.PB(mhm);
    return true;
  }
  return false;
}vector<bool> swpp;
vector<int> answ;
vector<int> gg;
bool traver(int smth, int l, int r) {
  int current = curr;
  while (true) {
    if (swpp[current]) {
      swpp[current]=!swpp[current];
      if (outgoers[current].F==curr) return false;
      if (l+1!=r) {
        r = (l+r)/2;
        current = outgoers[current].F;
      }
      else {
        outgoers[current].F = -gg[smth];
        return true;
      }
    }
    else {
      swpp[current]=!swpp[current];
      if (outgoers[current].second==curr) return false;
      if (l+1!=r) {
        current = outgoers[current].second;
        l = (l+r)/2+1;
      }
      else {
        outgoers[current].second = -gg[smth];
        return true;
      }
    }
  }
}
void create_circuit(int m, std::vector<int> a) {
  gg = a;
  gg.PB(0);
  int n = a.size();
  outgoers.PB({0,0});
  int upper2 = getbigg(n+1);
  build(1, 0, upper2-1, n, upper2-1);
  for (auto &ele: outgoers) {
    if (ele.F==-1) ele.F=curr;
    if (ele.second==-1) ele.second=curr;
  }
  vector C(m+1, -curr);
  swpp.assign(outgoers.size(), true);
  answ.assign(upper2, -1);
  int current = 0;
  LOO(i,0, upper2-1) {
    if (traver(current, 0, upper2-1)) {
      current++;
    }
  }
  vector<int> X((int)outgoers.size()-1), Y((int)(outgoers.size())-1);
  LOO(i,1,outgoers.size()-1) {
    X[i-1] = -outgoers[i].F;
    Y[i-1] = -outgoers[i].second;
  }
  answer(C, X, Y);
}

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