| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 849878 | tosivanmak | Arranging Shoes (IOI19_shoes) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct pairs{
ll l,r;
bool operator<(const pairs& p)const{
vector<ll>v;
v.push_back(l);
v.push_back(r);
v.push_back(p.l);
v.push_back(p.r);
ll cnt=0;
for(int i=0;i<4;i++){
for(int j=i-1;j>=0;j--){
if(v[j]<v[i]){
cnt++;
}
}
}
vector<ll>v2;
v2.push_back(p.l);
v2.push_back(p.r);
v2.push_back(l);
v2.push_back(r);
ll cnt2=0;
for(int i=0;i<4;i++){
for(int j=i-1;j>=0;j--){
if(v2[j]<v2[i]){
cnt2++;
}
}
}
// cout<<1;
return cnt>cnt2;
}
};
struct FEN{
vector<ll>fen;
void init(ll n){
fen.resize(n+5);
for(int i=0;i<=n+4;i++){
fen[i]=0;
}
}
void upd(ll n, ll m, ll val){
for(int i=n;i<=m;i+=i&(-i)){
fen[i]+=val;
// cout<<i;
}
}
ll sum(ll e){
ll su=0;
while(e>=1){
su+=fen[e];
e-=e&(-e);
}
// cout<<1;
return su;
}
};
long long count_swaps(std::vector<int> s) {
vector<ll>make;
vector<ll>adj[s.size()+5],adj2[s.size()+5];
for(int i=0;i<s.size();i++){
if(s[i]<0){
make.push_back(abs(s[i]));
adj[abs(s[i])].push_back(i+1);
}
else{
adj2[s[i]].push_back(i+1);
}
}
ll ptr[s.size()+5];
for(int i=0;i<=s.size()+4;i++){
ptr[i]=0;
}
vector<pairs>bruh;
// for(auto u: adj[2]){
// cout<<u<<" ";
// }
for(int i=0;i<make.size();i++){
bruh.push_back({adj[make[i]][ptr[make[i]]],adj2[make[i]][ptr[make[i]]]});
ptr[make[i]]++;
}
sort(bruh.begin(),bruh.end());
vector<ll>real;
for(int i=0;i<bruh.size();i++){
real.push_back(bruh[i].l);
real.push_back(bruh[i].r);
}
// for(auto u: real){
// cout<<u<<" ";
// }
FEN f;
f.init(s.size());
ll ans=0;
for(int i=0;i<real.size();i++){
ans+=f.sum(s.size())-f.sum(real[i]);
f.upd(real[i],s.size(),1);
}
return ans;
// return 0;
}
#ifndef ONLINE_JUDGE
int main() {
int n;
cin>>n;
vector<int> S(2 * n);
for (int i = 0; i < 2 * n; i++){
cin>>S[i];
}
long long result = count_swaps(S);
cout<<result<<"\n";
return 0;
}
#endif