| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1332405 | kokokai | Arranging Shoes (IOI19_shoes) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define fi first
#define se second
struct fenwick{
vector<ll> fw;
int n;
fenwick(int _n){
n=_n;
fw.resize(n+2,0);
}
void update(int idx,ll val){
for(;idx<=n;idx+=idx&(-idx)){
fw[idx] += val;
}
}
ll get(int idx){
ll res=0;
for(;idx>0;idx -= idx&(-idx)){
res += fw[idx];
}
return res;
}
};
ll cntinverse(vector<int> s){
int n=s.size();
fenwick fw(n);
ll ans=0;
for(int i=0;i<n;i++){
ans += fw.get(n-s[i]);
fw.update(n-s[i]+1,1);
}
return ans;
}
ll minswap(vector<int> a,vector<int> b){
int n=a.size();
vector<int> cntnum(n+1,0);
vector<vector<int>> pos(n+1);
for(int i=0;i<n;i++){
pos[a[i]].push_back(i+1);
}
for(int i=0;i<n;i++){
b[i]=pos[b[i]][cntnum[b[i]]];
cntnum[b[i]]++;
}
ll ans=cntinverse(b);
return ans;
}
ll count_swap(vector<int> s){
int n=s.size();
vector<vector<int>> left(n+1),right(n+1);
for(int i=0;i<n;i++){
if(s[i]<0){
left[abs(s[i])].push_back(i+1);
}else{
right[abs(s[i])].push_back(i+1);
}
}
bool ok=1;
for(int i=0;i<=n;i++){
if(left[i].size() != right[i].size()){
ok=0;
}
}
if(!ok){
return -1;
}
vector<int> cntnum(n+1,0);
vector<int> c(n);
int inow=0;
for(int i=0;i<n;i++){
if(s[i]<0){
c[2*inow]=left[abs(s[i])][cntnum[abs(s[i])]];
c[2*inow+1]=right[abs(s[i])][cntnum[abs(s[i])]];
cntnum[abs(s[i])]++;
inow++;
}
}
ll ans=cntinverse(c);
return ans;
}