結果
問題 | No.2029 Swap Min Max Min |
ユーザー | olphe |
提出日時 | 2022-08-05 21:25:48 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,363 bytes |
コンパイル時間 | 1,490 ms |
コンパイル使用メモリ | 139,216 KB |
実行使用メモリ | 11,752 KB |
最終ジャッジ日時 | 2023-10-14 00:02:58 |
合計ジャッジ時間 | 5,244 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,348 KB |
testcase_01 | AC | 2 ms
4,352 KB |
testcase_02 | WA | - |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | AC | 21 ms
5,556 KB |
testcase_06 | AC | 44 ms
9,428 KB |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | AC | 13 ms
4,752 KB |
testcase_11 | WA | - |
testcase_12 | AC | 28 ms
6,988 KB |
testcase_13 | WA | - |
testcase_14 | AC | 64 ms
10,364 KB |
testcase_15 | WA | - |
testcase_16 | AC | 63 ms
10,324 KB |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | AC | 62 ms
10,384 KB |
testcase_20 | AC | 63 ms
10,368 KB |
testcase_21 | AC | 64 ms
10,404 KB |
testcase_22 | AC | 63 ms
10,324 KB |
testcase_23 | AC | 73 ms
11,752 KB |
testcase_24 | AC | 72 ms
11,416 KB |
testcase_25 | AC | 52 ms
10,332 KB |
testcase_26 | AC | 52 ms
10,420 KB |
testcase_27 | AC | 1 ms
4,352 KB |
testcase_28 | AC | 2 ms
4,348 KB |
testcase_29 | AC | 2 ms
4,352 KB |
testcase_30 | AC | 2 ms
4,352 KB |
testcase_31 | AC | 2 ms
4,348 KB |
testcase_32 | WA | - |
testcase_33 | AC | 2 ms
4,348 KB |
testcase_34 | AC | 1 ms
4,348 KB |
testcase_35 | AC | 1 ms
4,352 KB |
testcase_36 | AC | 2 ms
4,352 KB |
testcase_37 | AC | 1 ms
4,352 KB |
testcase_38 | AC | 76 ms
10,952 KB |
testcase_39 | AC | 62 ms
10,392 KB |
testcase_40 | AC | 57 ms
10,152 KB |
testcase_41 | AC | 81 ms
10,944 KB |
testcase_42 | AC | 81 ms
10,964 KB |
testcase_43 | AC | 62 ms
10,340 KB |
testcase_44 | AC | 87 ms
11,532 KB |
ソースコード
#include "iostream" #include "climits" #include "list" #include "queue" #include "stack" #include "set" #include "functional" #include "algorithm" #include "string" #include "map" #include "unordered_map" #include "unordered_set" #include "iomanip" #include "cmath" #include "random" #include "bitset" #include "cstdio" #include "numeric" #include "cassert" #include "ctime" using namespace std; //constexpr long long int MOD = 1000000007; constexpr long long int MOD = 998244353; constexpr double EPS = 1e-8; //int N, M, K, T, H, W, L, R; long long int N, M, K, T, H, W, L, R; class Add_Segment_Tree { vector<long long int>v; long long int ret; int num; long long int Update(int place) { if (place >= v.size() / 2) { return v[place]; } v[place] = Update(place * 2) + Update(place * 2 + 1); return v[place]; } public: Add_Segment_Tree(int n) { n++; num = 1; while (num < n * 2)num *= 2; v.resize(num, 0); } void Add(int place, long long int num, bool update) { place += v.size() / 2; v[place] += num; if (!update)return; place /= 2; while (place) { v[place] = v[place * 2] + v[place * 2 + 1]; place /= 2; } } void TopDown() { Update(1); } long long int Sum(int a, int b) { ret = 0; b++; for (a += num / 2, b += num / 2; a < b; a >>= 1, b >>= 1) { if (a & 1)ret += v[a++]; if (b & 1)ret += v[--b]; } return ret; } }; int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> N; vector<int>v(N); for (auto& i : v)cin >> i; auto w = v; sort(w.begin(), w.end()); cout << w[N / 2 - 1] << " "; vector<int>a; vector<int>b; for (int i = 0; i < N; i++) { if (v[i] <= N / 2)b.push_back(i); else a.push_back(i); } long long ans = LLONG_MAX; { vector < int>x; for (int i = 0; i < N / 2; i++) { x.push_back(a[i]); x.push_back(b[i]); } if (x.size() < v.size())x.push_back(a.back()); Add_Segment_Tree asg(N); long long c = 0; for (auto i : x) { c += asg.Sum(i, N - 1); asg.Add(i, 1, true); } ans = min(ans, c); } if (N % 2 == 0) { vector < int>x; for (int i = 0; i < N / 2; i++) { x.push_back(b[i]); x.push_back(a[i]); } if (x.size() < v.size())x.push_back(a.back()); Add_Segment_Tree asg(N); long long c = 0; for (auto i : x) { c += asg.Sum(i, N - 1); asg.Add(i, 1, true); } ans = min(ans, c); } cout << ans << endl; }