Submission #501503

#TimeUsernameProblemLanguageResultExecution timeMemory
501503fusabileArranging Shoes (IOI19_shoes)C++17
10 / 100
0 ms204 KiB
#include <bits/stdc++.h> using namespace std; #ifdef LOCAL #include "dbg.h" #else #define dbg(...) #endif #define sz(s) (int)(s).size() #define all(x) (x).begin(), (x).end() typedef long long ll; const int inf = INT_MAX; const int dx[] = {1, -1, 0, 0}; const int dy[] = {0, 0, 1, -1}; ll count_swaps(vector<int> S) { int n = sz(S); ll ans = 0; map<int, queue<int>> mp; for (int i = 0; i < n; i++) mp[S[i]].push(i); for (int i = 0; i < n;) { if (S[i] == inf) { i++; continue; } vector<array<int, 3>> best; // best[i] = {left_index, right_index, swap_count} int j = mp[-S[i]].front(); assert(j < n); if (S[i] < 0) best.push_back({i, j, j - i - 1}); else best.push_back({j, i, j - i}); i++; if (abs(S[i]) != abs(S[i-1])) { if (S[i] < 0) best.push_back({i, j, j - i + 1}); else best.push_back({j, i, j - i + 2}); } i--; sort(best.begin(), best.end(), [](auto &x, auto &y) { return x[2] < y[2]; }); auto [x, y, z] = best[0]; ans += z; mp[S[x]].pop(); mp[S[y]].pop(); S[x] = inf; S[y] = inf; } 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...