| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 302587 | AmineTrabelsi | Arranging Shoes (IOI19_shoes) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
using namespace std;
typedef long long ll;
#define ff first
#define ss second
#define em emplace_back
#define mp make_pair
typedef pair<int,int> ii;
const int M = 1e5 + 10;
int tree[M*2];
int x;
void add(int k,int n){
while(k <= x){
tree[k] += n;
k += k& - k;
}
}
int sum(int i){
int res = 0;
while(i >= 1){
res += tree[i];
i -= i& - i;
}
return res;
}
vector<ii> ord[M];
ll count_swaps(std::vector<int> s){
ll res = 0;
x = s.size();
int n = x/2;
for(int i=0;i<x;i++){
ord[abs(s[i])].em(mp(s[i],i));
}
vector<ii> v;
for(int i=1;i<=n;i++){
sort(ord[i].begin(),ord[i].end());
for(int j=0;j<ord[i].size()/2;j++){
int f = ord[i][j].second,
s = ord[i][j+(ord[i].size()/2)].second;
if(f > s){
swap(f,s);
res++;
}
v.em(mp(f+1,s+1));
}
}
//cout << res << endl;
sort(v.begin(),v.end());
//for(auto i:v)cout << i.ff << " " << i.ss << endl;
for(int i=1;i<=n*2;i++)add(i,1);
for(auto i:v){
res += sum(i.ss-1)-sum(i.ff);
add(i.ss,-1);
add(i.ff,-1);
}
return res;
}