oj.uz

Submission #1106063

# Submission time Handle Problem Language Result Execution time Memory
1106063 2024-10-29T06:44:00 Z alcoholic Swap (BOI16_swap) C++17
100 / 100
 665 ms 13820 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define endl "\n"
#define ll long long
#define mp make_pair
#define ins insert
#define lb lower_bound
#define pb push_back
#define ub upper_bound
#define lll __int128
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
const int inf = 1e9;
int main() {
  ios_base::sync_with_stdio(0); cin.tie(NULL);
  int n;
  cin >> n;
  int a[n + 1];
  for(int i = 1; i <= n; ++i)
    cin >> a[i];
  // for each int, we need to know it's pair
  vector<int> v[n + 1];
  bool to_par[n + 1];
  memset(to_par, 0, sizeof(to_par));
  // go to parent with the values you have and find whether it is possible
  // fi -> idx, se -> moment when split
  int res[n + 1];
  v[1].pb(a[1]);
  // have counter of how many allowed to go to parent, so -- instead?
  for(int i = 1; i <= n; ++i) {
    pair<int, int> mn = mp(inf, inf);
    int cur = i;
    cerr << i << endl;
    while(true) {
      // mark where we should stop, the child of that should be not allowed to go
      // cerr << "AT PARENT " << cur << endl;
      if(v[cur].size()) {
        sort(v[cur].begin(), v[cur].end(), greater<int>());
        mn = min(mn, mp(v[cur].back(), cur));
      }
      // cerr << "DEBUG " << cur << endl;
      if(!to_par[cur])
        break;
      cur >>= 1;
    }
    // keep in mind that we can use both left and right childs too
    // left child -> to_par[right] false
    if(2 * i <= n) {
      mn = min(mn, mp(a[2 * i], 2 * i));
    }
    if(2 * i + 1 <= n) {
      mn = min(mn, mp(a[2 * i + 1], 2 * i + 1));
    }
    // cerr << "FOUND MN " << mn.fi << " " << mn.se << endl;
    // cerr << "TO_PAR " << to_par[i] << endl;
    res[i] = mn.fi;
    if(mn.se == 2 * i) {
      // use a[2 * i] here
      to_par[2 * i] = 1;
      // push right if exists
      if(2 * i + 1 <= n)
        v[2 * i + 1].pb(a[2 * i + 1]);
    }
    else if(mn.se == 2 * i + 1) {
      // use a[2 * i + 1] here
      // whatever in v[i] or parents of it can go to both directions
      to_par[2 * i] = to_par[2 * i + 1] = 1;
      v[i].pb(a[2 * i]);
    }
    else {
      // any child can not go to parent
      // set in our direction that it is not allowed (unless it is at current, then it doesn't matter)
      if(2 * i <= n)
        v[2 * i].pb(a[2 * i]);
      if(2 * i + 1 <= n)
        v[2 * i + 1].pb(a[2 * i + 1]);
      if(mn.se != i) {
        int cur = i;
        // cerr << cur << " " << mn.se << endl;
        while(cur != mn.se) {
          to_par[cur] = 0;
          cur >>= 1;
        }
        // cerr << "DELETE " << mn.se << endl;
        v[mn.se].pop_back();
      }
    }
  }
  for(int i = 1; i <= n; ++i)
    cout << res[i] << " ";
  cout << endl;
  return 0;
}

Subtask #1
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 456 KB Output is correct
5 Correct 1 ms 336 KB Output is correct

Subtask #2
11.0 / 11.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 456 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
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct

Subtask #3
27.0 / 27.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 456 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
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 4 ms 336 KB Output is correct
12 Correct 4 ms 336 KB Output is correct
13 Correct 4 ms 336 KB Output is correct
14 Correct 4 ms 336 KB Output is correct
15 Correct 4 ms 336 KB Output is correct

Subtask #4
20.0 / 20.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 456 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
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 4 ms 336 KB Output is correct
12 Correct 4 ms 336 KB Output is correct
13 Correct 4 ms 336 KB Output is correct
14 Correct 4 ms 336 KB Output is correct
15 Correct 4 ms 336 KB Output is correct
16 Correct 153 ms 3644 KB Output is correct
17 Correct 145 ms 3664 KB Output is correct
18 Correct 151 ms 3656 KB Output is correct
19 Correct 149 ms 3596 KB Output is correct
20 Correct 152 ms 3480 KB Output is correct

Subtask #5
32.0 / 32.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 456 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
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 4 ms 336 KB Output is correct
12 Correct 4 ms 336 KB Output is correct
13 Correct 4 ms 336 KB Output is correct
14 Correct 4 ms 336 KB Output is correct
15 Correct 4 ms 336 KB Output is correct
16 Correct 153 ms 3644 KB Output is correct
17 Correct 145 ms 3664 KB Output is correct
18 Correct 151 ms 3656 KB Output is correct
19 Correct 149 ms 3596 KB Output is correct
20 Correct 152 ms 3480 KB Output is correct
21 Correct 580 ms 13724 KB Output is correct
22 Correct 633 ms 13776 KB Output is correct
23 Correct 611 ms 13764 KB Output is correct
24 Correct 624 ms 13640 KB Output is correct
25 Correct 665 ms 13820 KB Output is correct