제출 #228760

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