Submission #1022681

#TimeUsernameProblemLanguageResultExecution timeMemory
1022681CodeAssignmentArranging Shoes (IOI19_shoes)C++17
100 / 100
123 ms29012 KiB
#include <bits/stdc++.h> #include <bits/extc++.h> using namespace std; using namespace __gnu_pbds; #define rep(i, a, b) for(int i = a; i < (b); ++i) #define all(x) begin(x), end(x) #define sz(x) (int)(x).size() #define trav(a, x) for (auto &a : x) #define pb push_back #define el "\n"; //#define dbg(x) cerr << "\e[92m" << #x << " = " << x << "\e[97m" << el; #define dbg(x) typedef long long ll; typedef pair<int, int> pii; typedef vector<int> vi; typedef vector<ll> vll; template<class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; void example() { Tree<int> t, t2; t.insert(8); auto it = t.insert(10).first; assert(it == t.lower_bound(9)); assert(t.order_of_key(10) == 1); assert(t.order_of_key(11) == 2); //assert(t.order_of_key(9) == 1); assert(*t.find_by_order(0) == 8); t.join(t2); } /* dies on 4 1 2 1 -1 -2 -1 3 -3 */ ll count_swaps(vector<int> S) { /* auto dbgarray = [&](vi &arr, string s) -> void { cerr << s << " is: "; rep(i, 0, sz(arr)) { cerr << arr[i] << " "; } cerr << el; }; */ Tree<ll> t; assert(sz(S) % 2 == 0); ll n = sz(S) / 2; // number of pairs vi a = S; vector<set<ll>> pos(2 * n + 1); rep(i, 0, 2*n) { pos[a[i] + n].insert(i); } vector<bool> done(2 * n); ll ans = 0; ll ind = 0; while(ind < 2 * n) { if (done[ind]) { ind++; continue; } ll cur = a[ind]; auto nxt = pos[-cur + n].upper_bound(ind); ll bigger = t.order_of_key(-(*nxt)); ll bigger2 = t.order_of_key(-ind); dbg(bigger); dbg(bigger2); assert(nxt != pos[-cur + n].end()); assert(a[*nxt] == -cur); dbg(ind); dbg(cur); dbg(*nxt); dbg(a[*nxt]); dbg(sz(pos[-cur + n])); trav(x, pos[-cur +n]) { ll tmp = x; dbg(tmp); } ans += (*nxt) - ind - (cur < 0 ? 1 : 0) + bigger - bigger2; dbg(ans); t.insert(-(*nxt)); pos[-cur + n].erase(*nxt); done[ind] = 1; done[*nxt] = 1; // TODO: we aren't actually updating the array, so how do we handle ind ind++; /* vi temp; rep(i, 0, ind) { temp.pb(a[i]); } temp.pb((cur < 0 ? cur : -cur)); temp.pb((cur < 0 ? -cur : cur)); rep(i, ind + 1, 2*n) { if (i == *nxt) continue; temp.pb(a[i]); } assert(sz(temp) == 2 * n); swap(a, temp); */ } return ans; }

Compilation message (stderr)

shoes.cpp: In function 'll count_swaps(std::vector<int>)':
shoes.cpp:83:7: warning: unused variable 'tmp' [-Wunused-variable]
   83 |    ll tmp = x;
      |       ^~~
#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...