Submission #1290739

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290739		lambd47	Arranging Shoes (IOI19_shoes)	C++20	45 / 100	121 ms	140636 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+4);
    vector<queue<int>> lst(n+4);
    int m=n/2;
    vector<int> par(4+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;
    for(auto a:negs){
        ord[a]=at++;
        ord[par[a]]=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: 0 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15