Submission #114244

#	Time	Username	Problem	Language	Result	Execution time	Memory
114244		faustaadp	Mechanical Doll (IOI18_doll)	C++17	100 / 100	146 ms	16268 KiB

doll

#include "doll.h"
#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll n,m,te,ki[404040],ka[404040],con[404040],i,N;
vector<ll> isi;
ll cak(ll aa)
{
  ll ii;
  for(ii=0;ii<30;ii++)
  {
    if((1<<ii)>=aa)
      return (1<<ii);
  }
  return 0;
}
ll buat(ll aa,ll bb,ll cc,ll dd)
{
  if(bb==1)
  {
    isi.pb(cc);
    return -cc;
  }
  if(aa==0)
    return 1;
  else
  {
    te++;
    ll tem=te;
    ll x=min(bb/2,aa);
    ki[tem]=-buat(aa-x,bb/2,cc,dd*2);
    ka[tem]=-buat(x,bb/2,cc+dd,dd*2);
    return tem;
  }
}     
void create_circuit(int M, std::vector<int> A) 
{
  n=A.size();
  m=M;
  std::vector<int> C(M + 1);
  N=cak(n+1);
 // cout<<N<<"\n";
  C[0]=-buat(n+1,N,0,1);
  for(i=1;i<=m;i++)
    C[i]=-1;
  sort(isi.begin(),isi.end());
  for(i=n+1;i<(ll)isi.size();i++)
    A.pb(-1);
  A.pb(0);  
  for(i=0;i<(ll)isi.size();i++)
  {
    //cout<<isi[i]<<" _ "<<i<<"\n";
    con[isi[i]]=i;
  }
  for(i=1;i<=te;i++)
  {
    if(ki[i]>=0)
      ki[i]=A[con[ki[i]]];
    if(ka[i]>=0)
      ka[i]=A[con[ka[i]]];
  }
  std::vector<int> X(te);
  std::vector<int> Y(te);
  for(i=1;i<=te;i++)
  {
    //cout<<i<<" "<<ki[i]<<" "<<ka[i]<<"\n";
    X[i-1]=ki[i];
    Y[i-1]=ka[i];
  }
  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