Submission #776021

#	Time	Username	Problem	Language	Result	Execution time	Memory
776021		I_Love_EliskaM_	Mechanical Doll (IOI18_doll)	C++14	100 / 100	190 ms	32600 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define ll long long
#define pb push_back
#define all(x) x.begin(), x.end()
const ll inf = 1e18;
#define pi pair<int,int>
#define f first
#define s second

void mysim(vector<int> c, vector<int> x, vector<int> y) {
  int p=0;
  int z=1;
  int k=x.size();
  vector<int> s(k,0);
  while (z||p) {
    if (!p) {
      z=0; p=c[p];
    } else if (p>0) {
      cout<<p<<"->\n";
      p=c[p];
    } else {
      cout<<"? "<<p<<'\n';
      int i=-p-1;
      if (s[i]==0) p=x[i];
      else p=y[i];
      s[i]^=1;
    }
  }
}

void create_circuit(int m, vector<int>a) {
  int n=a.size();
  vector<int> c(m+1,-1); c[0]=a[0];
  int sz=1; while (2*sz<n) sz<<=1;
  vector<int> x(2*sz-1,-1), y(2*sz-1,-1);
  forn(i,sz-1) x[i]=2*i+1, y[i]=2*i+2;
  forn(i,sz-1) x[i]=-1-x[i], y[i]=-1-y[i];
  vector<int> s(2*sz-1,1);
 
  vector<pi> z;
  forn(it,2*sz) {
    int p=0;
    while (p<sz-1) {
      s[p]^=1;
      p=2*p+1+s[p];
    }
    s[p]^=1;
    z.pb({p,s[p]});
  }

  if (n&1) {
    c[0]=-1;
    a.pb(0);
    ++n;
  } else {
    forn(i,n-1) a[i]=a[i+1];
    a[n-1]=0;
  }

  vector<int> ok(2*sz);
  forn(i,sz-n/2) ok[sz-1+i]=1;

  int p=0;
  for(auto&it:z) {
    if (ok[it.f]) continue;
    if (it.s) y[it.f]=a[p];
    else x[it.f]=a[p];
    ++p;
  }
  
  vector<int> fs,sc;
  set<int> st; forn(i,2*sz-1) st.insert(i);
  for(int i=2*sz-2; i>=0; --i) {
    if (x[i]==-1 && y[i]==-1) {
      st.erase(i);
      if (i&1) {
        x[(i-1)/2]=-1;
      } else {
        y[(i-1)/2]=-1;
      }
    }
  }
  forn(i,2*sz-1) {
    if (!st.count(i)) continue;
    fs.pb(x[i]);
    sc.pb(y[i]);
  }

  map<int,int> comp; int mex=0;
  for(auto&x:st) comp[x]=mex++;
  forn(i,sz-1) {
    if (fs[i]<0) fs[i]=-1-comp[-fs[i]-1];
    if (sc[i]<0) sc[i]=-1-comp[-sc[i]-1];
  }
 
  answer(c,fs,sc);
}

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