제출 #382171

#제출 시각아이디문제언어결과실행 시간메모리
382171valerikkSwap (BOI16_swap)C++17
68 / 100
500 ms262148 KiB
//#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) {
      |                     ~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...