Submission #1185741

#TimeUsernameProblemLanguageResultExecution timeMemory
1185741nikaa123Arranging Shoes (IOI19_shoes)C++20
0 / 100
2 ms2628 KiB
#include "shoes.h" #include <bits/stdc++.h> #define pb push_back using namespace std; const int N = 1e5 + 5; int t[4 * N]; int fix[N]; vector<vector<int>> v(N); void update(int node, int tl, int tr, int pos) { if (tl == tr) { t[node]++; return; } int mid = (tl + tr) / 2; if (pos <= mid) { update(node * 2, tl, mid, pos); } else { update(node * 2 + 1, mid + 1, tr, pos); } t[node] = t[node * 2] + t[node * 2 + 1]; } int getsum(int node, int tl, int tr, int l, int r) { if (l > r) return 0; if (tl == l && tr == r) { return t[node]; } int mid = (tl + tr) / 2; return getsum(node * 2, tl, mid, l, min(r, mid)) + getsum(node * 2 + 1, mid + 1, tr, max(mid + 1, l), r); } long long count_swaps(std::vector<int> s) { int n = s.size(); s.insert(s.begin(), 0); for (int i = 1; i <= n; i++) { s[i] += n / 2; v[s[i]].pb(i); } long long op = 0; for (int i = 1; i <= n; i++) { if (fix[i]) continue; int a = s[i]; int b = (a <= n / 2) ? a + n / 2 : a - n / 2; int l = 0, r = v[b].size() - 1; int ib = -1; while (l <= r) { int mid = (l + r) / 2; if (v[b][mid] > i) { ib = v[b][mid]; r = mid - 1; } else { l = mid + 1; } } int shift = getsum(1, 1, n, i + 1, ib - 1); op += (ib - i - 1 - shift); if (a > n / 2) op++; update(1, 1, n, ib); fix[ib] = 1; } return op; }
#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...