oj.uz

Submission #112912

# Submission time Handle Problem Language Result Execution time Memory
112912 2019-05-22T16:17:04 Z imaxblue Mechanical Doll (IOI18_doll) C++17
100 / 100
 226 ms 29120 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define x first
#define y second
#define pii pair<int, int>
#define p3i pair<pii, int>
#define pll pair<ll, ll>
#define p3l pair<pll, ll>
#define vi vector<int>
#define vpii vector<pii>
#define vp3i vector<p3i>
#define vpll vector<pll>
#define vp3l vector<p3l>
#define lseg L, (L+R)/2, N*2
#define rseg (L+R)/2+1, R, N*2+1
#define ub upper_bound
#define lb lower_bound
#define pq priority_queue
#define MN 1000000007
#define fox(k, x) for (int k=0; k<x; ++k)
#define fox1(k, x) for (int k=1; k<=x; ++k)
#define foxr(k, x) for (int k=x-1; k>=0; --k)
#define fox1r(k, x) for (int k=x; k>0; --k)
#define ms multiset
#define flood(x) memset(x, 0x3f3f3f3f, sizeof x)
#define drain(x) memset(x, 0, sizeof x)
#define rng() ((rand() << 14)+rand())
#define scan(X) do{while((X=getchar())<'0'); for(X-='0'; '0'<=(_=getchar()); X=(X<<3)+(X<<1)+_-'0');}while(0)
char _;
#define pi 3.14159265358979323846

void answer(vector<int> C, vector<int> X, vector<int> Y);/*{
  fox(l, C.size()) cout << C[l] << ' '; cout << endl;
  fox(l, X.size()){
    cout << X[l] << ' ' << Y[l] << endl;
  }
}*/

int n, n2, m, cnt, x[800005], y[800005], a2[300000];
vector<int> a;
map<int, int> com;
vector<int> c, x2, y2;
vector<pii> v;
int solve(int L, int R, int N){
  if (L == R){
    return a2[L];
  }
  x[N] = solve(lseg);
  y[N] = solve(rseg);
  //cout << N << ' ' << L << ' ' << R << ' ' << x[N] << ' ' << y[N] << endl;
  if (x[N] == -1 && y[N] == -1){
      x[N] = y[N] = 0x3f3f3f3f;
      return -1;
  }
  return -N;
}
int rev(int x){
  int res = 0;
  for (int l = 0; l < 22; ++l, x/=2){res = res*2+x%2;}
  return res;
}
void create_circuit(int M, vector<int> A){
  m = M;
  fox(l, m+1){
    c.pb(-1);
  }
  flood(x);
  flood(y);
  a = A;
  a.pb(0);
  n2 = n = a.size();
  for (; (n&-n) != n; ++n){
    a2[n - n2] = -1;
  }
  for(int l = n - n2; l < n; ++l){
    v.pb(mp(rev(l), l));
  }
  sort(v.begin(), v.end());
  fox(l, n2){
    a2[v[l].y] = a[l];
  }
  fox(l, n){
    //cout << a2[l] << ' ';
  }
  //cout << endl;

  //return;
  solve(0, n-1, 1);
  fox1(l, 2*n){
    //cout << l << ' ' << x[l] << ' ' << y[l] << endl;
    if (x[l] != 0x3f3f3f3f){
      com[-l] = --cnt;
      //cout << "*" << l << ' ' << cnt << endl;
    }
  }
  fox1(l, 2*n){
    if (x[l] != 0x3f3f3f3f){
      if (x[l] >= 0) x2.pb(x[l]);
      else x2.pb(com[x[l]]);
      if (y[l] >= 0) y2.pb(y[l]);
      else y2.pb(com[y[l]]);
    }
  }
  answer(c, x2, y2);
}
/*
int main(){
  int n, m, a;
  vector<int> A;
  cin >> m >> n;
  fox(l, n){
    cin >> a;
    A.pb(a);
  }
  create_circuit(m, A);
  return 0;
}*/
/*
4 4
1 2 1 3
*/

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6476 KB Output is correct
2 Correct 69 ms 15388 KB Output is correct
3 Correct 77 ms 14788 KB Output is correct
4 Correct 6 ms 6512 KB Output is correct
5 Correct 20 ms 7856 KB Output is correct
6 Correct 105 ms 18892 KB Output is correct
7 Correct 5 ms 6564 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6476 KB Output is correct
2 Correct 69 ms 15388 KB Output is correct
3 Correct 77 ms 14788 KB Output is correct
4 Correct 6 ms 6512 KB Output is correct
5 Correct 20 ms 7856 KB Output is correct
6 Correct 105 ms 18892 KB Output is correct
7 Correct 5 ms 6564 KB Output is correct
8 Correct 121 ms 21544 KB Output is correct
9 Correct 130 ms 22316 KB Output is correct
10 Correct 200 ms 29120 KB Output is correct
11 Correct 5 ms 6476 KB Output is correct
12 Correct 5 ms 6448 KB Output is correct
13 Correct 5 ms 6476 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6476 KB Output is correct
2 Correct 69 ms 15388 KB Output is correct
3 Correct 77 ms 14788 KB Output is correct
4 Correct 6 ms 6512 KB Output is correct
5 Correct 20 ms 7856 KB Output is correct
6 Correct 105 ms 18892 KB Output is correct
7 Correct 5 ms 6564 KB Output is correct
8 Correct 121 ms 21544 KB Output is correct
9 Correct 130 ms 22316 KB Output is correct
10 Correct 200 ms 29120 KB Output is correct
11 Correct 5 ms 6476 KB Output is correct
12 Correct 5 ms 6448 KB Output is correct
13 Correct 5 ms 6476 KB Output is correct
14 Correct 226 ms 28508 KB Output is correct
15 Correct 136 ms 21092 KB Output is correct
16 Correct 172 ms 28436 KB Output is correct
17 Correct 5 ms 6476 KB Output is correct
18 Correct 4 ms 6476 KB Output is correct
19 Correct 4 ms 6476 KB Output is correct
20 Correct 187 ms 28920 KB Output is correct
21 Correct 5 ms 6476 KB Output is correct
22 Correct 5 ms 6528 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6476 KB Output is correct
2 Correct 128 ms 20316 KB Output is correct
3 Correct 118 ms 20328 KB Output is correct
4 Correct 192 ms 27276 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6476 KB Output is correct
2 Correct 128 ms 20316 KB Output is correct
3 Correct 118 ms 20328 KB Output is correct
4 Correct 192 ms 27276 KB Output is correct
5 Correct 169 ms 28420 KB Output is correct
6 Correct 176 ms 28096 KB Output is correct
7 Correct 195 ms 28276 KB Output is correct
8 Correct 177 ms 27936 KB Output is correct
9 Correct 142 ms 20400 KB Output is correct
10 Correct 177 ms 27904 KB Output is correct
11 Correct 168 ms 27620 KB Output is correct
12 Correct 104 ms 20648 KB Output is correct
13 Correct 120 ms 20920 KB Output is correct
14 Correct 110 ms 20916 KB Output is correct
15 Correct 128 ms 21040 KB Output is correct
16 Correct 7 ms 6940 KB Output is correct
17 Correct 103 ms 20280 KB Output is correct
18 Correct 109 ms 20544 KB Output is correct
19 Correct 120 ms 20564 KB Output is correct
20 Correct 187 ms 27804 KB Output is correct
21 Correct 162 ms 27540 KB Output is correct
22 Correct 162 ms 27620 KB Output is correct