| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1040947 | idas | Arranging Shoes (IOI19_shoes) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "shoes.h"
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin); i<(end); i++)
#define pb push_back
#define int long long
using namespace std;
typedef long long ll;
typedef vector<int> vi;
const int N=2e5+10;
int n, cn[N], pos[N];
vi p_pos, n_pos[N];
void upd_cn(int p, int x)
{
p++;
for(int i=p; i<N; i+=i&(-i)) cn[i]+=x;
}
int get_cn_pref(int p)
{
p++;
ll ret=0;
for(int i=p; i>0; i-=i&(-i)) ret+=cn[i];
return ret;
}
int get_cn(int x, int y)
{
x++; y++;
return get_cn_pref(y)-get_cn_pref(x-1);
}
void upd_pos(int p, int x)
{
p++;
for(int i=p; i<N; i+=i&(-i)) pos[i]+=x;
}
int add_pos(int p)
{
p++;
ll ret=0;
for(int i=p; i>0; i-=i&(-i)) ret+=pos[i];
return ret;
}
int get_pos(int p)
{
return p+add_pos(p);
}
void shift(int p, int x)
{
int l=p, r=n-1;
while(l<r){
int m=(l+r+1)/2;
if(get_cn(p, m)<=x) l=m;
else r=m-1;
}
upd_pos(p, -1);
upd_pos(l+1, 1);
}
long long count_swaps(vector<int> s) {
ll true_ans=1e18;
n=s.size();
FOR(i, 0, n)
{
if(s[i]<0) n_pos[-s[i]].pb(i);
else p_pos.pb(i);
}
FOR(i, 0, n) upd_cn(i, 1);
ll ans=0;
int in=n-1;
while(!p_pos.empty()){
int pos=p_pos.back();
p_pos.pop_back();
upd_cn(pos, -1);
int true_pos=get_pos(pos);
assert(in>=true_pos);
ll dist=in-true_pos; ans+=dist;
in--;
shift(pos, dist);
int neg_pos=n_pos[s[pos]].back();
n_pos[s[pos]].pop_back();
upd_cn(neg_pos, -1);
int true_neg_pos=get_pos(neg_pos);
dist=in-true_neg_pos; ans+=dist;
in--;
shift(neg_pos, dist);
}
true_ans=min(true_ans, ans);
// FOR(i, 0, n) s[i]=-s[i];
FOR(i, 0, N) cn[i]=pos[i]=0, n_pos[i].clear();
p_pos.clear();
reverse(s.begin(), s.end());
FOR(i, 0, n)
{
if(s[i]>0) n_pos[s[i]].pb(i);
else p_pos.pb(i);
}
FOR(i, 0, n) upd_cn(i, 1);
ans=0;
in=n-1;
while(!p_pos.empty()){
int pos=p_pos.back();
p_pos.pop_back();
upd_cn(pos, -1);
int true_pos=get_pos(pos);
assert(in>=true_pos);
ll dist=in-true_pos; ans+=dist;
in--;
shift(pos, dist);
int neg_pos=n_pos[-s[pos]].back();
n_pos[-s[pos]].pop_back();
upd_cn(neg_pos, -1);
int true_neg_pos=get_pos(neg_pos);
dist=in-true_neg_pos; ans+=dist;
in--;
shift(neg_pos, dist);
}
true_ans=min(true_ans, ans);
return true_ans;
}