oj.uz

Submission #776017

# Submission time Handle Problem Language Result Execution time Memory
776017 2023-07-07T08:33:23 Z I_Love_EliskaM_ Mechanical Doll (IOI18_doll) C++14
26 / 100
 244 ms 14772 KB 
    #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[i].f]=a[i];
        y[z[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];
      }
     
      answer(c,fs,sc);
    }

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 44 ms 5024 KB Output is correct
3 Correct 42 ms 4568 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 7 ms 1364 KB Output is correct
6 Correct 83 ms 6936 KB Output is correct
7 Correct 0 ms 212 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 44 ms 5024 KB Output is correct
3 Correct 42 ms 4568 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 7 ms 1364 KB Output is correct
6 Correct 83 ms 6936 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 119 ms 9788 KB Output is correct
9 Correct 114 ms 9608 KB Output is correct
10 Correct 244 ms 14772 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 44 ms 5024 KB Output is correct
3 Correct 42 ms 4568 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 7 ms 1364 KB Output is correct
6 Correct 83 ms 6936 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 119 ms 9788 KB Output is correct
9 Correct 114 ms 9608 KB Output is correct
10 Correct 244 ms 14772 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 222 ms 14084 KB Output is correct
15 Correct 146 ms 7132 KB Output is correct
16 Correct 199 ms 10724 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 217 ms 13348 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct

Subtask #5
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB state 'Y'
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB state 'Y'
2 Halted 0 ms 0 KB -