Submission #1112250

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112250		epicci23	Mechanical Doll (IOI18_doll)	C++17	100 / 100	97 ms	12960 KiB

doll

#include "bits/stdc++.h"
#include "doll.h"
//#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;

const int INF = (int) 1e9;
vector<int> x,y,state,hm;
int p=1,p2=0;

void give_index(int rt,int l,int r){
  int mid = (l+r)/2;
  if(r-l==1){
    if(mid+1>sz(hm)) x[rt]=-1;
    return;
  }
  if(mid+1>sz(hm)) x[rt]=-1;
  else{
    x[rt]=-(++p);
    x.push_back(-INF);
    y.push_back(-INF);
    state.push_back(0);
    give_index(-x[rt],mid+1,r);
  }
  y[rt]=-(++p);
  x.push_back(-INF);
  y.push_back(-INF);
  state.push_back(0);
  give_index(-y[rt],l,mid);
}
 
void make_leaf(int rt){
  if(state[rt]==0){
    state[rt]^=1;
    if(x[rt]==-INF) x[rt]=hm[p2++];
    else make_leaf(-x[rt]);
  }
  else{
    state[rt]^=1;
    if(y[rt]==-INF) y[rt]=hm[p2++];
    else make_leaf(-y[rt]);
  }
}

void create_circuit(int m, vector<int> a){
  vector<int> c(m+1);
  
  x.push_back(-INF);
  y.push_back(-INF);
  state.push_back(0);


  a.push_back(0);
  x.push_back(-INF);
  y.push_back(-INF);
  state.push_back(0);

  hm=a;
  for(int i=0;i<=m;i++) c[i]=-1;
   
  int nd=1;
  while(nd<sz(hm)) nd<<=1;

  give_index(1,1,nd);
  for(int i=0;i<sz(hm);i++) make_leaf(1);


  reverse(all(x));
  x.pop_back();
  reverse(all(x));

  reverse(all(y));
  y.pop_back();
  reverse(all(y));

  answer(c, x, y);
}

/*void _(){
  int _n,_m;
  cin >> _n >> _m;
  vector<int> xd;
  for(int i=0;i<_n;i++){
    int a; cin >> a;
    xd.push_back(a);
  }
  create_circuit(_m,xd);
  cout << sz(x) << '\n';
  for(int i=0;i<sz(x);i++){
    cout << x[i] << ' ' << y[i] << '\n';
  }
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}*/

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