Submission #587657

#	Time	Username	Problem	Language	Result	Execution time	Memory
587657		Koosha_mv	Mechanical Doll (IOI18_doll)	C++14	10 / 100	29 ms	5300 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<x.F<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first

const int N=2e5+99;

int n,m,lg,cnt;
vector<int> A,B;
int g[N][2];

void solve(int now,int ted){
  if(ted==2) return ;
  g[now][0]=++cnt;
  solve(cnt,ted/2);
  g[now][1]=++cnt;
  solve(cnt,ted/2);
}

void create_circuit(int _n,vector<int> _A) {
  f(i,0,N) g[i][0]=g[i][1]=N;
  n=_n,m=_A.size(),A=_A;
  f(i,0,30) if((1<<i)>m){
    lg=i;
    break;
  }
  cnt=lg;
  f(i,1,lg){
    if(m&(1<<(lg-i))){
      g[i][0]=++cnt;
      solve(cnt,(1<<(lg-i)));
    }
    else{
      g[i][0]=1;
    }
    g[i][1]=i+1;
  }
  if(bit(m,0)==0){
    g[lg][0]=1;
  }
  g[lg][1]=0;
  //eror(g[1][0]);
  //eror(g[1][1]);
  int now=1,p=0,prt=0;
  while(now!=0){
    prt++;
    if(now<0){
      now=1;
      continue ;
    }
    if(g[now][0]==N){
      g[now][0]=-A[p]; p++;
    }
    swap(g[now][0],g[now][1]);
    now=g[now][1];
    if(prt>200) break;
  }
  vector<int> adj(n+1,-1);
  vector<int> X,Y;
  f(i,1,cnt+1) X.pb(-g[i][0]),Y.pb(-g[i][1]);
  //dbgv(adj);
  //dbgv(X);
  //dbgv(Y);
  answer(adj,X,Y);
}
/*
2 2
1 2
*/

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