| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1147662 | gulmix | Arranging Shoes (IOI19_shoes) | C++20 | 0 ms | 0 KiB |
#include "molecules.h"
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
#define oset tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
const int MAXN = 200005;
struct bit{
int tree[MAXN];
void add(int x, int v){
for(int i = x; i < MAXN; i += i & -i)tree[i] += v;
}
int query(int x){
int ans = 0;
for(int i = x; i; i -= i & -i)ans+=tree[i];
return ans;
}
}bit;
ll count_swaps(vector<int> a){
int n = size(a) / 2;
int tot = 0;
vector<pair<int, int>> v;
vector<pair<int, int>> ord[MAXN];
for(int i = 0; i < a.size(); i++){
ord[abs(a[i])].emplace_back(a[i], i);
}
for(int i = 1; i <= n; i++){
sort(all(ord[i]));
for(int j = 0; j < ord[i].size() / 2; j++){
int l = ord[i][j].second;
int r = ord[i][j + ord[i].size()/2].second;
if(l > r){
swap(l, r);
tot++;
}
v.emplace_back(l + 1, r + 1);
}
}
for(int i = 1; i <= 2*n; i++)bit.add(i, 1);
sort(all(v));
for(auto &i: v){
tot += bit.query(i.second - 1) - bit.query(i.first);
bit.add(i.first, -1);
bit.add(i.second, -1);
}
return tot;
}
//int main(){
// ios::sync_with_stdio(false);
// cin.tie(0);
// //ifstream cin("cycle2.in");
// //ofstream cout("cycle2.out");
// vector<int> b = {15, 17, 16, 18};
// vector<int> a = find_subset(10, 20, b);
// for(auto &i: a)cout << i << ' ';
//}