Submission #439046

#TimeUsernameProblemLanguageResultExecution timeMemory
439046sean617Arranging Shoes (IOI19_shoes)C++17
50 / 100
290 ms276572 KiB
#include "shoes.h" #define N 500005 #include <cstdio> #include <iostream> #include <queue> using namespace std; typedef long long ll; ll n, t, ans = 0, pa[N], s[N]; queue<ll> qu[200005]; ll f_num(int p) { if (p < 0) return (n - p); else return p; } ll f(ll p) { ll re =0; while (p >= 1) { re += s[p]; p -= (p & -p); } return re; } void g(ll p) { while (p <= n) { s[p]++; p += (p & -p); } } long long count_swaps(std::vector<int> a) { ll i, t, rt, tt, mi; n = a.size(); for (i = 1; i <= n; i++) { t = f_num(a[i - 1]); rt = f_num(-a[i - 1]); if (qu[rt].empty()) { qu[t].push(i); } else { tt = qu[rt].front(); qu[rt].pop(); pa[tt] = i; pa[i] = tt; } } for (i = 1; i <= n; i++) { if (i < pa[i]) { mi = f(pa[i]) - f(i); ans += (pa[i] - i - 1 - mi); if (a[i - 1] > 0) ans++; g(pa[i]); } } 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...