제출 #382171

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
382171		valerikk	Swap (BOI16_swap)	C++17	68 / 100	500 ms	262148 KiB

swap

//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<pair<int, int>> result;
const int N = 2e5 + 7;

inline void upd(result &a, const result &b) {
    if (!b.empty() && (a.empty() || b < a)) a = b;
}

inline void merge(const result &a, const result &b, result &res) {
    int i = 0, j = 0;
    while (i < a.size() || j < b.size()) {
        if (i == a.size()) {
            res.push_back(b[j++]);
        } else if (j == b.size()) {
            res.push_back(a[i++]);
        } else {
            if (a[i] < b[j]) {
                res.push_back(a[i++]);
            } else res.push_back(b[j++]);
        }
    }
}

int n, x[N];
vector<int> vals[N];
vector<result> dp[N];

inline int get_ind(int v, int val) {
    /*auto it = lower_bound(vals[v].begin(), vals[v].end(), val);
    assert(it != vals[v].end() && *it == val);*/
    return lower_bound(vals[v].begin(), vals[v].end(), val) - vals[v].begin();
}

void go(int v) {
    /*if (v > n) return;
    go(2 * v);
    go(2 * v + 1);*/
    if (2 * v > n) {
        for (int i = 0; i < vals[v].size(); ++i) dp[v][i] = {{v, vals[v][i]}};
        /*for (int i = 0; i < vals[v].size(); ++i) {
            for (auto w : dp[v][i]) cout << w.first << " " << w.second << endl;
            cout << endl;
        }*/
        return;
    }
    if (2 * v + 1 > n) {
        for (int i = 0; i < vals[v].size(); ++i) {
            for (int f = 0; f < 2; ++f) {
                int val = vals[v][i], val2 = x[2 * v];
                if (f) swap(val, val2);
                result cur = {{v, val}};
                int ind = get_ind(2 * v, val2);
                for (auto w : dp[2 * v][ind]) cur.push_back(w);
                upd(dp[v][i], cur);
            }
        }
        return;
    }
    //return;
    for (int i = 0; i < vals[v].size(); ++i) {
        for (int left = 0; left < 2; ++left) {
            for (int right = 0; right < 2; ++right) {
                int val = vals[v][i], l = x[2 * v], r = x[2 * v + 1];
                if (left) swap(val, l);
                if (right) swap(val, r);
                if (l < val || r < val) continue;
                result cur = {{v, val}};
                int lind = get_ind(2 * v, l), rind = get_ind(2 * v + 1, r);
                merge(dp[2 * v][lind], dp[2 * v + 1][rind], cur);
                upd(dp[v][i], cur);
            }
        }
    }
}

int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif 
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> x[i];
    for (int i = 1; i <= n; ++i) {
        vals[i].push_back(x[i]);
        for (int j = i; j > 1; j >>= 1) {
            vals[i].push_back(x[j >> 1]);
            vals[i].push_back(x[j ^ 1]);
        }
        sort(vals[i].begin(), vals[i].end());
        dp[i].resize(vals[i].size());
    }
    /*for (int i = 1; i <= n; ++i) {
        cout << "vals[" << i << "]: ";
        for (auto val : vals[i]) cout << val << " ";
        cout << endl;
    }
    return 0;*/
    //go(1);
    int ptr = n;
    for (int i = n; i >= 1; --i) {
        while (ptr > 2 * i + 1) {
            dp[ptr].clear();
            dp[ptr].shrink_to_fit();
            --ptr;
        }
        go(i);
    }
    int ind = get_ind(1, x[1]);
    for (auto i : dp[1][ind]) cout << i.second << " ";
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

swap.cpp: In function 'void merge(const result&, const result&, result&)':
swap.cpp:15:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     while (i < a.size() || j < b.size()) {
      |            ~~^~~~~~~~~~
swap.cpp:15:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     while (i < a.size() || j < b.size()) {
      |                            ~~^~~~~~~~~~
swap.cpp:16:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |         if (i == a.size()) {
      |             ~~^~~~~~~~~~~
swap.cpp:18:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |         } else if (j == b.size()) {
      |                    ~~^~~~~~~~~~~
swap.cpp: In function 'void go(int)':
swap.cpp:43:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |         for (int i = 0; i < vals[v].size(); ++i) dp[v][i] = {{v, vals[v][i]}};
      |                         ~~^~~~~~~~~~~~~~~~
swap.cpp:51:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         for (int i = 0; i < vals[v].size(); ++i) {
      |                         ~~^~~~~~~~~~~~~~~~
swap.cpp:64:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for (int i = 0; i < vals[v].size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 11 / 11
• Subtask 3: 27 / 27
• Subtask 4: 20 / 20
• Subtask 5: 0 / 32