제출 #1263974

#제출 시각아이디문제언어결과실행 시간메모리
1263974BlockOGArranging Shoes (IOI19_shoes)C++20
100 / 100
641 ms32256 KiB
#include <bits/stdc++.h> // mrrrow meeow :3 // go play vivid/stasis now! it's free on steam #define fo(i, a, b) for (auto i = (a); i < (b); i++) #define of(i, a, b) for (auto i = (b); i-- > (a);) #define f first #define s second #define pb push_back #define pob pop_back #define lb lower_bound #define ub upper_bound #define be(a) a.begin(), a.end() using namespace std; int ____init = [] { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); return 0; }(); int bit[200001]; void add(int i, int v) { for (i++; i <= 200000; i += i & -i) bit[i] += v; } int get(int i) { int res = 0; for (i++; i > 0; i -= i & -i) res += bit[i]; return res; } long long count_swaps(vector<int> s) { long long n = s.size() / 2; map<int, set<int>> m; fo(i, 0, 2 * n) { m[s[i]].insert(i); add(i, 1); } add(0, -1); long long res = 0; int zero = 0; fo(i, 0, n) { while (get(zero) != 0) zero++; int first_curr = zero; int first_other = *m[-s[first_curr]].begin(); m[s[first_curr]].erase(first_curr); m[s[first_other]].erase(first_other); if (s[first_curr] > 0) swap(first_curr, first_other); cerr << s[first_curr] << ' ' << s[first_other] << endl; res += get(first_curr); add(first_curr, -1); res += get(first_other); add(first_other, -1); } return res; }
#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...