Submission #776015

#	Time	Username	Problem	Language	Result	Execution time	Memory
776015		I_Love_EliskaM_	Mechanical Doll (IOI18_doll)	C++14	70.40 / 100	229 ms	36412 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();
      map<int,int> cnt;
      int mx=0;
      for(auto&x:a) {
        cnt[x]++;
        mx=max(mx,cnt[x]);
      }
      if (mx<=4) {
        vector<int> c(m+1,0);
        c[0]=a[0];
        vector<int> x,y;
        int nxt=0;
        for(auto&it:cnt) {
          int v=it.f, k=it.s;
          if (k==1) continue;
          if (k==2) {
            x.pb(0), y.pb(0);
            c[v]=-1-nxt++;
          } else {
            x.pb(-1-(nxt+1)), y.pb(-1-(nxt+2));
            forn(i,2) x.pb(0), y.pb(0);
            if (k==3) y[nxt+1]=-1-(nxt);
            c[v]=-nxt-1;
            nxt+=3;
          }
        }
        map<int,int> ok;
        a.pb(0);
        for(int i=0;i<n;++i) {
          int k=cnt[a[i]];
          if (k==1) {
            c[a[i]]=a[i+1];
          } else if (k==2) {
            if (ok[a[i]]) {
              y[-c[a[i]]-1]=a[i+1];
            } else {
              ++ok[a[i]];
              x[-c[a[i]]-1]=a[i+1];
            }
          } else if (k==3) {
            if (ok[a[i]]==0) {
              x[-1-x[-c[a[i]]-1]]=a[i+1];
            } else if (ok[a[i]]==1) {
              x[-1-y[-c[a[i]]-1]]=a[i+1];
            } else {
              y[-1-y[-c[a[i]]-1]]=a[i+1];
            }
            ++ok[a[i]];
          } else {
            if (ok[a[i]]==0) {
              x[-1-x[-c[a[i]]-1]]=a[i+1];
            } else if (ok[a[i]]==1) {
              x[-1-y[-c[a[i]]-1]]=a[i+1];
            } else if (ok[a[i]]==2) {
              y[-1-x[-c[a[i]]-1]]=a[i+1];
            } else {
              y[-1-y[-c[a[i]]-1]]=a[i+1];
            }
            ++ok[a[i]];
          }
        }
        answer(c,x,y);
        return;
      }
     
      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;
      }
     
      forn(i,n/2) {
        x[z[2*sz-n/2+i].f]=a[i];
        y[z[2*sz-n/2+i].f]=a[n/2+i];
      }
      
      vector<int> fs,sc;
      set<int> st; forn(i,2*sz-1) st.insert(i);
      forn(i,2*sz-1) {
        if (x[i]==-1) {
          st.erase(i);
          //cout<<"! "<<i<<' '<<x[i]<<'\n';
          if (i&1) {
            fs[(i-1)/2]=y[i];
          } else {
            sc[(i-1)/2]=y[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';
      //}
      //mysim(c,fs,sc);
      //return;
     
      answer(c,fs,sc);
    }

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