제출 #1047348

#제출 시각아이디문제언어결과실행 시간메모리
1047348MercubytheFirstArranging Shoes (IOI19_shoes)C++17
100 / 100
47 ms15308 KiB
#include <bits/stdc++.h> #include "shoes.h" using ll = long long; using namespace std; long long inversion_count(vector<int> v) { ll ans = 0; int n = v.size(); for(int& i : v) i += 1; int bit[n + 1]{}; for(int i = 0; i < n; ++i) { assert(1 <= v[i] and v[i] <= n); for(int idx = n; idx > 0; idx -= (idx&-idx)) { ans += bit[idx]; } for(int idx = v[i]; idx > 0; idx -= (idx&-idx)) { ans -= bit[idx]; } for(int idx = v[i]; idx <= n; idx += (idx&-idx)) { bit[idx]++; } } return ans; } long long count_swaps(std::vector<int> s) { // ll ans = 0; int n = (int)s.size() / 2; vector<vector<int> > r(n + 1), l(n + 1); for(int i = 0; i < 2*n; ++i) { if(s[i] < 0) { l[abs(s[i])].push_back(i); } else { r[s[i]].push_back(i); } } for(int i = 1; i <= n; ++i) { reverse(l[i].begin(), l[i].end()); reverse(r[i].begin(), r[i].end()); } vector<int> order(2*n, -1); vector<bool> used(2*n, false); int idx = 0; for(int i = 0; i < 2*n; ++i) { if(used[i]) { continue; } const int sz = abs(s[i]); int lshoe, rshoe; if(s[i] < 0) { lshoe = i; rshoe = r[sz].back(); while(used[rshoe]) { r[sz].pop_back(); rshoe = r[sz].back(); } r[sz].pop_back(); } else if(s[i] > 0) { rshoe = i; lshoe = l[sz].back(); while(used[lshoe]) { l[sz].pop_back(); lshoe = l[sz].back(); } l[sz].pop_back(); } else assert(false); assert(!used[lshoe] and !used[rshoe]); assert(order[lshoe] == -1 and order[rshoe] == -1); used[lshoe] = used[rshoe] = true; order[lshoe] = idx; order[rshoe] = idx+1; idx += 2; } // for(int x : order) // cout << x << ' '; // cout << endl; return inversion_count(order); }
#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...