Submission #775406

#	Time	Username	Problem	Language	Result	Execution time	Memory
775406		I_Love_EliskaM_	Mechanical Doll (IOI18_doll)	C++14	47 / 100	204 ms	38176 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) {
  vector<int> c(m+1,-1); c[0]=a[0];
  int n=a.size();
  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]});
  }
  
  a.pb(0);
  for (int i=2*sz-1; 2*sz-i<=n; --i) {
    if (z[i].s) y[z[i].f]=a[n-(2*sz-i-1)];
    else x[z[i].f]=a[n-(2*sz-i-1)];
  }

  vector<int> fs,sc;
  set<int> st; forn(i,2*sz-1) st.insert(i);
  forn(i,2*sz-1) {
    if (y[i]==-1) {
      st.erase(i);
      //cout<<"! "<<i<<' '<<x[i]<<'\n';
      if (i&1) {
        fs[(i-1)/2]=x[i];
      } else {
        sc[(i-1)/2]=x[i];
      }
    } else {
      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];
  }

  forn(i,fs.size()) {
    //cout<<fs[i]<<' '<<sc[i]<<'\n';
  }
  //return;

  answer(c,fs,sc);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:4:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define forn(i,n) for(int i=0;i<n;++i)
......
   84 |   forn(i,fs.size()) {
      |        ~~~~~~~~~~~              
doll.cpp:84:3: note: in expansion of macro 'forn'
   84 |   forn(i,fs.size()) {
      |   ^~~~

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