oj.uz

Submission #775717

# Submission time Handle Problem Language Result Execution time Memory
775717 2023-07-06T19:54:15 Z I_Love_EliskaM_ Mechanical Doll (IOI18_doll) C++14
47 / 100
 260 ms 33724 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[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 (!st.count(i)) continue;
    if (x[i]==-1) {
      st.erase(i);
      //cout<<"! "<<i<<' '<<x[i]<<'\n';
      int j=(i-1)/2;
      int p=sc[j];
      fs[j]=x[-1-p];
      sc[j]=y[-1-p];
      st.erase(-1-p);
    } 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,x,y);
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 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
9.0000000036 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 212 KB Output is partially correct
2 Correct 97 ms 19280 KB Output is correct
3 Partially correct 171 ms 24832 KB Output is partially correct
4 Partially correct 198 ms 31424 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 212 KB Output is partially correct
2 Correct 97 ms 19280 KB Output is correct
3 Partially correct 171 ms 24832 KB Output is partially correct
4 Partially correct 198 ms 31424 KB Output is partially correct
5 Partially correct 232 ms 33724 KB Output is partially correct
6 Partially correct 260 ms 32700 KB Output is partially correct
7 Partially correct 228 ms 33048 KB Output is partially correct
8 Partially correct 221 ms 32088 KB Output is partially correct
9 Partially correct 203 ms 24888 KB Output is partially correct
10 Partially correct 198 ms 31924 KB Output is partially correct
11 Partially correct 203 ms 31476 KB Output is partially correct
12 Partially correct 177 ms 24916 KB Output is partially correct
13 Correct 121 ms 20128 KB Output is correct
14 Partially correct 195 ms 26040 KB Output is partially correct
15 Partially correct 197 ms 26484 KB Output is partially correct
16 Partially correct 4 ms 1108 KB Output is partially correct
17 Correct 109 ms 19344 KB Output is correct
18 Correct 106 ms 19200 KB Output is correct
19 Partially correct 178 ms 24924 KB Output is partially correct
20 Partially correct 208 ms 31568 KB Output is partially correct
21 Partially correct 204 ms 31400 KB Output is partially correct
22 Partially correct 202 ms 31456 KB Output is partially correct