제출 #1290743

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290743		lambd47	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	112 ms	140660 KiB

shoes

#include<bits/stdc++.h>
#include "shoes.h"
using namespace std;

#define ll long long
#define L(i,j,k) for(int i=(j);i<=(k);i++)
#define R(i,j,k) for(int i=(j);i>=(k);i--)
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()



long long count_swaps(std::vector<int> vec) {
    int n=sz(vec);
    vector<int> negs;
    vector<int> ord(n+2);
    vector<queue<int>> lst(n+2);
    int m=n/2;
    vector<int> par(2+n);
    L(i,1,n){
        int a=vec[i-1];
        if(a<0)negs.push_back(i);
        lst[a+m].push(i);
        if(!lst[a+m].empty() && !lst[m-a].empty()){
            int x=lst[a+m].front();
            lst[a+m].pop();
            int y=lst[m-a].front();
            lst[m-a].pop();
            par[x]=y;
            par[y]=x;
        }
    }
    int at=1;
    L(i,1,n){
        if(ord[i]!=0)continue;
        if (vec[i-1]<0){
        ord[i]=at++;
        ord[par[i]]=at++;
        }else{
            ord[par[i]]=at++;
            ord[i]=at++;
        }
    }

    //L(i,1,n)cout<<par[i];
    vector<int> rord(n+1,0);
    L(i,1,n){
        rord[ord[i]]=i;
    }
    vector<int> bt(n+2);
    auto upd=[&](int id)->void{
        while(id<n+1){
            bt[id]++;
            id+=(id&(-id));
        }
    };
    auto query=[&](int id)->int{
        int ret=0;
        while(id>0){
            ret+=bt[id];
            id-=(id&(-id));
        }
        return ret;
    };

    ll ans=0;
    L(i,1,n){
        ans+=query(n)-query(rord[i]);
        upd(rord[i]);
    }
    return ans;

}
/*
ok, primeiro pareio depois conto a qntd de inversoes e gg
*/

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15