제출 #228710

#제출 시각아이디문제언어결과실행 시간메모리
228710hhh07Arranging Shoes (IOI19_shoes)C++14
45 / 100
1082 ms73336 KiB
#include <iostream> #include <algorithm> #include <vector> #include <cmath> #include <string> #include <queue> #include "shoes.h" using namespace std; typedef long long ll; vector<ll> t; ll getSum(ll idx){ ll sum = 0; idx++; while (idx > 0){ sum += t[idx]; idx -= idx & (-idx); } return sum; } void updateF(ll n, ll idx, ll val){ idx++; while (idx <= n){ t[idx] += val; idx += idx & (-idx); } } ll count_swaps(vector<int> s){ ll n = s.size()/2; t.assign(2*n + 1, 0); vector<queue<ll>> cnt(n + 1, queue<ll> ()); queue<ll> q; vector<pair<int, int>> koristen(n + 1, make_pair(0, 0)); for (ll i = 2*n - 1; i >= 0; i--){ if (s[i] < 0){ if (koristen[-s[i]].first > 0){ cnt[-s[i]].push(-(i + 1)); koristen[-s[i]].first--; } else{ q.push(i); koristen[-s[i]].second++; } } else{ if (koristen[s[i]].second > 0){ cnt[s[i]].push(i + 1); koristen[s[i]].second--; } else{ q.push(i); koristen[s[i]].first++; } } } ll res = 0; ll pocetak = 2*n - 2; while(!q.empty()){ ll curr = q.front(); ll par = cnt[abs(s[curr])].front(); q.pop(); cnt[abs(s[curr])].pop(); if (par > 0) res++; else par = -par; par--; par += getSum(par); curr += getSum(curr); res += pocetak - par; updateF(2*n, par, -1); pocetak -= 2; } return res; }
#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...