Submission #737262

#	Time	Username	Problem	Language	Result	Execution time	Memory
737262		onlk97	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	360 ms	27448 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
long long bit[200020];
void add(int pos){
    for (int i=pos; i<200020; i+=i&(-i)) bit[i]++;
}
long long query(int pos){
    long long ans=0;
    for (int i=pos; i; i-=i&(-i)) ans+=bit[i];
    return ans;
}
long long count_swaps(std::vector<int> s) {
	int n=s.size();
    map <int,vector <int> > mp;
    for (int i=0; i<n; i++) mp[s[i]].push_back(i);
    for (auto&i:mp) reverse(i.second.begin(),i.second.end());
    int d[n];
    for (int i=0; i<n; i++) d[i]=0;
    int cur=1;
    for (int i=0; i<n; i++){
        if (d[i]) continue;
        if (s[i]<0){
            mp[s[i]].pop_back();
            d[i]=cur;
            d[mp[-s[i]].back()]=cur+1;
            mp[-s[i]].pop_back();
        } else {
            mp[s[i]].pop_back();
            d[i]=cur+1;
            d[mp[-s[i]].back()]=cur;
            mp[-s[i]].pop_back();
        }
        cur+=2;
    }
    long long ans=0;
    for (int i=s.size()-1; i>=0; i--){
        ans+=query(d[i]-1);
        add(d[i]);
    }
    return ans;
}

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