제출 #999501

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
999501		MarwenElarbi	Mechanical Doll (IOI18_doll)	C++17	100 / 100	106 ms	12424 KiB

doll

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ii pair<int,int>
const int nax=2e5+5;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void answer(std::vector<int> C, std::vector<int> X, std::vector<int> Y);
int n;
int cnt=0;
vector<int> tab(1<<18),x(1<<18),y(1<<18);
int build(int l,int r){
  if(l>=n){
    return -1;
  }else if(r-l<2){
    return 1;
  }else{
    int mid=(r+l)/2;
    int u=cnt++;
    y[u]=build(l,mid);
    x[u]=build(mid,r);
    return -u-1;
  }
}
void create_circuit(int M, std::vector<int> A){
  vector<int> C(M+1,-1);
  A.pb(0);
  n=A.size();
  int k=n;
  while(__builtin_popcount(k)!=1) k++;
  build(0,k);
  for(auto i:A){
    int cur=0;
    while(cur>=0){
      tab[cur]^=1;
      int w=-1-(tab[cur] ? x[cur] : y[cur]);
      if(w<0){
        (tab[cur] ? x[cur] : y[cur])=i;
        cur=-1;
      }else cur=w;
    }
  }
  x.resize(cnt);
  y.resize(cnt);
  answer (C,x,y);
}

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