oj.uz

답안 #868730

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
868730 2023-11-01T19:38:06 Z hazzle Swap (BOI16_swap) C++17
0 / 100
 0 ms 348 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx,avx2,fma")

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define all(m) (m).begin(), (m).end()
#define rall(m) (m).rbegin(), (m).rend()
#define vec vector
#define sz(a) (int) (a).size()
#define mpp make_pair
#define mt t make_tuple
#define RA ranges

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair <ll, ll> pll;
typedef pair <int, int> pii;
typedef tuple <int, int, int> tui;

template <typename T>
using prq = priority_queue <T>;

template <typename T>
using pgq = priority_queue <T, vec <T>, greater <T>>;

template <typename T>
using oset = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
#define ook order_of_key

template <typename T> bool umin(T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> bool umax(T &a, T b) { return a < b ? a = b, 1 : 0; }

inline int solve(){
      int n; cin >> n;
      vec <int> a(n + 1);
      for (int i = 1; i <= n; ++i) cin >> a[i];
      auto mrg = [&](int x, vec <int> lf, vec <int> rt){
            vec <int> res(1 + sz(lf) + sz(rt));
            res[0] = x;
            int p1 = 0, p2 = 0;
            int st = 1, pt = 1;
            while(pt < sz(res)){
                  for (int i = 0; i < st && p1 < sz(lf) && pt < sz(res); ++i){
                        res[pt++] = lf[p1++];
                  }
                  for (int i = 0; i < st && p2 < sz(rt) && pt < sz(res); ++i){
                        res[pt++] = rt[p2++];
                  }
                  st <<= 1;
            }
            return res;
      };
      vec <map <int, vec <int>>> dp(n + 1);
      auto _dp = [&](auto &&_dp, int i, int ai) -> vec <int> {
            if (dp[i].count(ai)) return dp[i][ai];
            int ls = 2 * i, rs = 2 * i + 1;
            if (ls > n) return dp[i][ai] = {ai};
            if (rs > n) return dp[i][ai] = {min(ai, a[ls]), max(ai, a[ls])};
            auto lol1 = _dp(_dp, ls, a[ls]);
            auto lol2 = _dp(_dp, rs, a[rs]);
            auto lol3 = _dp(_dp, ls, ai);
            auto lol4 = _dp(_dp, rs, ai);
            auto lol5 = _dp(_dp, rs, a[ls]);
            auto op1 = mrg(ai, lol1, lol2);
            auto op2 = mrg(a[ls], lol3, lol2);
            auto op3 = mrg(a[rs], lol1, lol4);
            auto op4 = mrg(a[rs], lol4, lol5);
            // 1 2 3
            // 2 1 3
            // 3 1 2
            // cout << i << " " << ai << ":\n";
            // cout << " "; for (auto &x: op1) cout << x << " "; cout << "\n";
            // cout << " "; for (auto &x: op2) cout << x << " "; cout << "\n";
            // cout << " "; for (auto &x: op3) cout << x << " "; cout << "\n";
            return dp[i][ai] = min({op1, op2, op3, op4});
      };
      vec <int> res = _dp(_dp, 1, a[1]);
      for (auto &i: res) cout << i << " ";
      return 0;
}

inline void precalc(){}

signed main(){
      //ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
      int tst = 1; //cin >> tst;
      precalc();
      while(tst--) solve();
      return 0;
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -