Submission #1290824

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290824		lucasdmy	Arranging Shoes (IOI19_shoes)	C++20	10 / 100	47 ms	69912 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e5+10;
long long int inv=0;
vector<int>ord(MAXN);
void merge_sort(int start, int end){
    if(start==end){
        return;
    }
    int middle=(start+end)>>1;
    merge_sort(start, middle);
    merge_sort(middle+1, end);
    int p1=start, p2=middle+1;
    vector<int>aux;
    while(p1!=middle+1 or p2!=end+1){
        if(p1==middle+1){
            aux.push_back(ord[p2]);
            p2++;
        }else if(p2==end+1){
            aux.push_back(ord[p1]);
            p1++;
        }else if(ord[p1]<ord[p2]){
            aux.push_back(ord[p1]);
            p1++;
        }else{
            aux.push_back(ord[p2]);
            p2++;
            inv+=middle+1-p1;
        }
    }
    for(int k=start;k<=end;k++){
        ord[k]=aux[k-start];
    }
}
long long int count_swaps(vector<int>v){
    int cont=0;
    vector<queue<int>>aux(MAXN);
    for(int k=0;k<v.size();k++){
        if(v[k]<0){
            cont++;
            ord[k]=2*cont-1;
            aux[-v[k]].push(2*cont);
        }
    }
    for(int k=0;k<v.size();k++){
        if(v[k]>0){
            ord[k]=aux[v[k]].front();
            aux[v[k]].pop();
        }
    }
    merge_sort(0, v.size()-1);
    return inv;
}
/*int main(){
    int n;
    cin>>n;
    vector<int>v(2*n);
    for(int k=0;k<2*n;k++){
        cin>>v[k];
    }
    cout<<count_swaps(v);
}*/

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