oj.uz

Submission #776021

# Submission time Handle Problem Language Result Execution time Memory
776021 2023-07-07T08:35:34 Z I_Love_EliskaM_ Mechanical Doll (IOI18_doll) C++14
100 / 100
 190 ms 32600 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();
  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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 51 ms 11192 KB Output is correct
3 Correct 65 ms 12880 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 8 ms 1364 KB Output is correct
6 Correct 88 ms 17088 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 51 ms 11192 KB Output is correct
3 Correct 65 ms 12880 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 8 ms 1364 KB Output is correct
6 Correct 88 ms 17088 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 102 ms 20524 KB Output is correct
9 Correct 147 ms 24980 KB Output is correct
10 Correct 174 ms 32600 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 51 ms 11192 KB Output is correct
3 Correct 65 ms 12880 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 8 ms 1364 KB Output is correct
6 Correct 88 ms 17088 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 102 ms 20524 KB Output is correct
9 Correct 147 ms 24980 KB Output is correct
10 Correct 174 ms 32600 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 175 ms 32208 KB Output is correct
15 Correct 135 ms 24236 KB Output is correct
16 Correct 190 ms 32108 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 182 ms 32384 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 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 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 96 ms 19744 KB Output is correct
3 Correct 132 ms 23832 KB Output is correct
4 Correct 182 ms 31556 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 96 ms 19744 KB Output is correct
3 Correct 132 ms 23832 KB Output is correct
4 Correct 182 ms 31556 KB Output is correct
5 Correct 171 ms 31876 KB Output is correct
6 Correct 176 ms 31692 KB Output is correct
7 Correct 173 ms 31832 KB Output is correct
8 Correct 172 ms 31648 KB Output is correct
9 Correct 143 ms 23836 KB Output is correct
10 Correct 172 ms 31532 KB Output is correct
11 Correct 171 ms 31492 KB Output is correct
12 Correct 147 ms 23880 KB Output is correct
13 Correct 99 ms 19904 KB Output is correct
14 Correct 141 ms 24112 KB Output is correct
15 Correct 138 ms 24300 KB Output is correct
16 Correct 3 ms 980 KB Output is correct
17 Correct 102 ms 19812 KB Output is correct
18 Correct 96 ms 19744 KB Output is correct
19 Correct 150 ms 23920 KB Output is correct
20 Correct 181 ms 31504 KB Output is correct
21 Correct 171 ms 31472 KB Output is correct
22 Correct 171 ms 31652 KB Output is correct