제출 #467387

#제출 시각아이디문제언어결과실행 시간메모리
467387ChrisGe123Arranging Shoes (IOI19_shoes)C++14
100 / 100
90 ms16380 KiB
#include "bits/stdc++.h" using namespace std; typedef long long ll; // #include <ext/pb_ds/tree_policy.hpp> // #include <ext/pb_ds/assoc_container.hpp> // using namespace __gnu_pbds; // template <class T> using Tree = tree<T, null_type, less<T>, // rb_tree_tag, tree_order_statistics_node_update>; const int maxn = 100002; #define mp make_pair #define pb push_back #define f first #define s second const int mod = 1e9+7; typedef pair<int, int> pii; int n; // for each shoe, we need the closest shoe to the right that is the opposite pair to it int r[2*maxn]; vector<int> eachsize[2*maxn]; //eachsize[i] contains the positions of the shoes of size i-n in order int sizepos[2*maxn]; //sizepos[i] tells us how many shoes of size i-n we've seen int fentree[2*maxn]; /* We need to figure out using some PURS thing how to get the number of elements between i and r[i] that have already been taken care of we can do this by just making a BIT where initially everything is 1, and then if the element i has been used, we make BIT[i] = 0 */ int lsb(int a) { return a & -a; } void change(int a, int c) { while (a <= 2*n) { fentree[a] += c; a += lsb(a); } } ll sum(int a) { ll s = 0; while (a > 0) { s += fentree[a]; a -= lsb(a); } return s; } ll count_swaps(vector<int> shoes) { n = shoes.size()/2; shoes.insert(shoes.begin(), 0); for (int i=1; i<=2*n; i++) { eachsize[shoes[i]+n].pb(i); } for (int i=1; i<=2*n; i++) { if (sizepos[shoes[i]+n] < (int) eachsize[-shoes[i]+n].size()) { int temp = eachsize[-shoes[i]+n][sizepos[shoes[i]+n]]; if (temp > i) { r[i] = temp; } } sizepos[shoes[i]+n]++; } ll ans = 0; for (int i=1; i<=2*n; i++) { change(i, 1); } for (int i=1; i<=2*n; i++) { if (r[i] != 0) { if (r[i] != i+1) { ans += sum(r[i]-1) - sum(i); //cerr << sum(r[i]-1) << " " << sum(i) << endl; } if (shoes[i] > 0) { ans++; } change(r[i], -1); } } return ans; }
#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...