제출 #228718

#제출 시각아이디문제언어결과실행 시간메모리
228718hhh07Arranging Shoes (IOI19_shoes)C++14
45 / 100
1089 ms139940 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>> cnt1(n + 1, queue<ll> ()), cnt2(n + 1, queue<ll> ()); queue<ll> q; for (ll i = 2*n - 1; i >= 0; i--){ if (s[i] < 0) cnt2[-s[i]].push(i); else cnt1[s[i]].push(i); } vector<bool> koristen(2*n, false); ll res = 0; ll pocetak = 2*n - 2; for (int i = 2*n - 1; i >= 0; i--){ if (koristen[i]) continue; ll curr = i, par; if (s[i] < 0){ res++; par = cnt1[-s[i]].front(); cnt1[-s[i]].pop(); cnt2[-s[i]].pop(); } else{ par = cnt2[s[i]].front(); cnt1[s[i]].pop(); cnt2[s[i]].pop(); } koristen[curr] = true; koristen[par] = true; par += getSum(par); 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...