제출 #228669

#제출 시각아이디문제언어결과실행 시간메모리
228669hhh07Arranging Shoes (IOI19_shoes)C++14
0 / 100
10 ms6912 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(4*100001, 0); 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); } } void build(vector<ll> arr, ll n){ for (int i = 1; i <= n; i++) t[i] = 0; for (int i = 0; i < n; i++) updateF(n, i, arr[i]); } ll count_swaps(vector<int> s){ int n = s.size()/2; vector<ll> arr(2*n, 0); build(arr, 2*n); vector<queue<int>> cnt(n, queue<int> ()); queue<int> q; vector<bool> koristen(2*n, false); for (int i = 2*n - 1; i >= 0; i--){ if (!koristen[s[i]]){ q.push(i); koristen[abs(s[i])] = true; } else{ cnt[abs(s[i])].push((i + 1)*abs(s[i])/s[i]); koristen[abs(s[i])] = false; } } int res = 0; int pocetak = 2*n - 1; while(!q.empty()){ int curr = q.front(); int par = cnt[abs(s[curr])].front(); q.pop(); cnt[abs(s[curr])].pop(); if (par < 0){ res++; par = -par; } par--; par += getSum(par); res += pocetak - par - 1; 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...