oj.uz

Submission #775406

# Submission time Handle Problem Language Result Execution time Memory
775406 2023-07-06T11:07:31 Z I_Love_EliskaM_ Mechanical Doll (IOI18_doll) C++14
47 / 100
 204 ms 38176 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) {
  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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 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 0 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 0 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 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 1 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 87 ms 19296 KB Output is correct
3 Partially correct 175 ms 37256 KB Output is partially correct
4 Partially correct 183 ms 37756 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 87 ms 19296 KB Output is correct
3 Partially correct 175 ms 37256 KB Output is partially correct
4 Partially correct 183 ms 37756 KB Output is partially correct
5 Partially correct 189 ms 38176 KB Output is partially correct
6 Partially correct 183 ms 37932 KB Output is partially correct
7 Partially correct 183 ms 38140 KB Output is partially correct
8 Partially correct 180 ms 37852 KB Output is partially correct
9 Partially correct 181 ms 37172 KB Output is partially correct
10 Partially correct 184 ms 37776 KB Output is partially correct
11 Partially correct 181 ms 37772 KB Output is partially correct
12 Partially correct 171 ms 37204 KB Output is partially correct
13 Correct 87 ms 19440 KB Output is correct
14 Partially correct 204 ms 37456 KB Output is partially correct
15 Partially correct 179 ms 37544 KB Output is partially correct
16 Partially correct 4 ms 1492 KB Output is partially correct
17 Correct 87 ms 19300 KB Output is correct
18 Correct 105 ms 19396 KB Output is correct
19 Partially correct 174 ms 37192 KB Output is partially correct
20 Partially correct 179 ms 37756 KB Output is partially correct
21 Partially correct 188 ms 37744 KB Output is partially correct
22 Partially correct 182 ms 37764 KB Output is partially correct