Submission #625215

#	Time	Username	Problem	Language	Result	Execution time	Memory
625215		John3_141592	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	80 ms	15836 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
#define ll long long
#define par pair<int,int>
#define f first
#define s second
#define ld long duble
#define ull unsigned long long
#define st short int

using namespace std;

int abi[1000006],N;

void add(int k){
    while(k<=N) abi[k]++,k+=k&-k;
}

ll query(int k){
    ll s=0;
    while(k) s+=abi[k],k-=k&-k;
    return s;
}

long long count_swaps(std::vector<int> vec) {
    int n=vec.size();
    vector <vector<int>> asd(n+1);
    int arr[n+1],a;
    for(int i=n-1;i>=0;i--) a=vec[i]+n/2,asd[a].push_back(i),arr[a]=asd[a].size()-1;
    N=n;
    ll solve=0;
    fill(abi,abi+n,0);
    bool vis[n];
    fill(vis,vis+n,false);
    for(int i=0;i<n;i++){
        if(vis[i]) continue;
        a=n/2-vec[i];
        while(arr[a]>=0 && asd[a][arr[a]]<i) arr[a]--;
        solve+=asd[a][arr[a]]-i-query(asd[a][arr[a]])+query(i);
        if(a>n/2) solve--;
        vis[asd[a][arr[a]]]=true;
        add(asd[a][arr[a]--]);
    }
    return solve;
}

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