제출 #742684

#제출 시각아이디문제언어결과실행 시간메모리
742684Andrei_ierdnAArranging Shoes (IOI19_shoes)C++17
100 / 100
371 ms148432 KiB
#include "shoes.h" #include <queue> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define ordered_set(x) tree<x, null_type, less<x>, rb_tree_tag, tree_order_statistics_node_update> long long count_swaps(std::vector<int> s) { long long i = 0, j = 0, aux = 0, ans = 0, dist = 0, n = s.size() / 2; bool viz[200100]; queue<int> lpoz[100100], rpoz[100100]; ordered_set(int) sset; for (i = 0; i < 2*n; i++) { if (s[i] < 0) { lpoz[-s[i]].push(i); } else { rpoz[s[i]].push(i); } sset.insert(i); viz[i] = false; } for (i = 0; i < 2*n; i++) { if (!viz[i]) { if (s[i] < 0) { lpoz[-s[i]].pop(); j = rpoz[-s[i]].front(); rpoz[-s[i]].pop(); aux = 0; } else { rpoz[s[i]].pop(); j = lpoz[s[i]].front(); lpoz[s[i]].pop(); aux = 1; } viz[i] = viz[j] = true; dist = sset.order_of_key(j) - sset.order_of_key(i) - 1 + aux; ans += dist; sset.erase(i); sset.erase(j); } } 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...