제출 #219176

#제출 시각아이디문제언어결과실행 시간메모리
219176sidiq_haArranging Shoes (IOI19_shoes)C++14
50 / 100
328 ms337520 KiB
#include<bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include "shoes.h" #define pb push_back #define fi first #define se second #define mp make_pair #define all(v) v.begin(), v.end() using namespace std; typedef long long LL; const LL MOD = 1e9 + 7; const double PI = 2 * acos(0); using namespace __gnu_pbds; typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> new_data_set; //order_of_key(x) = number of elements stricly smaller than x //find_by_order(x) = return x-th largest element bool flag[121212]; queue<int> kiri[121212], kanan[121212]; long long count_swaps(vector<int> s) { new_data_set tmp; int n = s.size(); LL ans2 = 0; vector<int> ans; for (int i = 0; i < n; i++) { if (s[i] < 0) kiri[-s[i]].push(i); else kanan[s[i]].push(i); } for (int i = 0; i < n; i++) { if (!flag[i]) { if (s[i] < 0) { int x = -s[i]; ans.pb(i); flag[i] = 1; kiri[x].pop(); int xx = kanan[x].front(); ans.pb(xx); flag[xx] = 1; kanan[x].pop(); } else { int x = s[i]; ans.pb(i); flag[i] = 1; kanan[x].pop(); int xx = kiri[x].front(); ans.pb(xx); flag[xx] = 1; kiri[x].pop(); } } } for (int i = 0; i < n; i += 2) { if (s[ans[i]] > 0) swap(ans[i], ans[i + 1]); } for (int i = 0; i < n; i++) { int cnt = tmp.order_of_key(ans[i]); cnt = i - cnt; ans2 += (ans[i] + cnt - i); tmp.insert(ans[i]); } return ans2; }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...