oj.uz

Submission #1112250

# Submission time Handle Problem Language Result Execution time Memory
1112250 2024-11-13T21:52:49 Z epicci23 Mechanical Doll (IOI18_doll) C++17
100 / 100
 97 ms 12960 KB 
#include "bits/stdc++.h"
#include "doll.h"
//#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;

const int INF = (int) 1e9;
vector<int> x,y,state,hm;
int p=1,p2=0;

void give_index(int rt,int l,int r){
  int mid = (l+r)/2;
  if(r-l==1){
    if(mid+1>sz(hm)) x[rt]=-1;
    return;
  }
  if(mid+1>sz(hm)) x[rt]=-1;
  else{
    x[rt]=-(++p);
    x.push_back(-INF);
    y.push_back(-INF);
    state.push_back(0);
    give_index(-x[rt],mid+1,r);
  }
  y[rt]=-(++p);
  x.push_back(-INF);
  y.push_back(-INF);
  state.push_back(0);
  give_index(-y[rt],l,mid);
}
 
void make_leaf(int rt){
  if(state[rt]==0){
    state[rt]^=1;
    if(x[rt]==-INF) x[rt]=hm[p2++];
    else make_leaf(-x[rt]);
  }
  else{
    state[rt]^=1;
    if(y[rt]==-INF) y[rt]=hm[p2++];
    else make_leaf(-y[rt]);
  }
}

void create_circuit(int m, vector<int> a){
  vector<int> c(m+1);
  
  x.push_back(-INF);
  y.push_back(-INF);
  state.push_back(0);


  a.push_back(0);
  x.push_back(-INF);
  y.push_back(-INF);
  state.push_back(0);

  hm=a;
  for(int i=0;i<=m;i++) c[i]=-1;
   
  int nd=1;
  while(nd<sz(hm)) nd<<=1;

  give_index(1,1,nd);
  for(int i=0;i<sz(hm);i++) make_leaf(1);


  reverse(all(x));
  x.pop_back();
  reverse(all(x));

  reverse(all(y));
  y.pop_back();
  reverse(all(y));

  answer(c, x, y);
}

/*void _(){
  int _n,_m;
  cin >> _n >> _m;
  vector<int> xd;
  for(int i=0;i<_n;i++){
    int a; cin >> a;
    xd.push_back(a);
  }
  create_circuit(_m,xd);
  cout << sz(x) << '\n';
  for(int i=0;i<sz(x);i++){
    cout << x[i] << ' ' << y[i] << '\n';
  }
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}*/

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 32 ms 4512 KB Output is correct
3 Correct 33 ms 4552 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 6 ms 1616 KB Output is correct
6 Correct 43 ms 7088 KB Output is correct
7 Correct 1 ms 336 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 32 ms 4512 KB Output is correct
3 Correct 33 ms 4552 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 6 ms 1616 KB Output is correct
6 Correct 43 ms 7088 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 62 ms 8176 KB Output is correct
9 Correct 68 ms 8760 KB Output is correct
10 Correct 82 ms 12960 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 32 ms 4512 KB Output is correct
3 Correct 33 ms 4552 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 6 ms 1616 KB Output is correct
6 Correct 43 ms 7088 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 62 ms 8176 KB Output is correct
9 Correct 68 ms 8760 KB Output is correct
10 Correct 82 ms 12960 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 96 ms 12820 KB Output is correct
15 Correct 62 ms 7920 KB Output is correct
16 Correct 79 ms 12400 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 336 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 79 ms 12780 KB Output is correct
21 Correct 1 ms 336 KB Output is correct
22 Correct 1 ms 336 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 63 ms 7148 KB Output is correct
3 Correct 58 ms 7104 KB Output is correct
4 Correct 79 ms 11156 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 63 ms 7148 KB Output is correct
3 Correct 58 ms 7104 KB Output is correct
4 Correct 79 ms 11156 KB Output is correct
5 Correct 81 ms 12168 KB Output is correct
6 Correct 85 ms 12116 KB Output is correct
7 Correct 83 ms 12072 KB Output is correct
8 Correct 97 ms 11816 KB Output is correct
9 Correct 61 ms 7152 KB Output is correct
10 Correct 79 ms 11736 KB Output is correct
11 Correct 83 ms 11536 KB Output is correct
12 Correct 62 ms 7356 KB Output is correct
13 Correct 70 ms 7616 KB Output is correct
14 Correct 63 ms 7740 KB Output is correct
15 Correct 65 ms 7872 KB Output is correct
16 Correct 2 ms 592 KB Output is correct
17 Correct 47 ms 7744 KB Output is correct
18 Correct 68 ms 7360 KB Output is correct
19 Correct 57 ms 7356 KB Output is correct
20 Correct 75 ms 11824 KB Output is correct
21 Correct 76 ms 11584 KB Output is correct
22 Correct 76 ms 11560 KB Output is correct