Submission #283167

#	Time	Username	Problem	Language	Result	Execution time	Memory
283167		Ruba_K	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	1096 ms	14276 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
using namespace std ;
vector<int > pos[200005];
vector<int>st ;
int idx ;
int binarysearch(int u){ sort(st.begin() , st.end());
    while(st.size() && st.back() > idx)st.pop_back();
    if(st.empty())return 0 ;

    if(st.back() < u)return 0 ;
    int l = 0 , r = st.size() , md ;
    while(l < r){
        md = (l + r) / 2 ;
        if(st[md] < u)l = md + 1 ;
        else r = md ;

    }
    return st.size() - l ;
}



long long count_swaps(vector<int> v) {
    int n = v.size() / 2 ;
    for(int i = 0 ; i < n * 2 ; i ++){
        pos[v[i] + n] .push_back(i) ;
    }
    long long ans = 0 ;

    for(int i = 2 * n - 1 ; i >= 0 ; i --){
        if(v[i] == 0)continue ;
        idx = i ;
        int p = v[i] * -1 + n ;
        pos[v[i] + n].pop_back();
        auto u = binarysearch(p);
        int sum = 0 ;


        v[pos[p].back()] = 0;
        sum = u ;
        sum = i - pos[p].back() - sum - 1 ;

        st.push_back(pos[p].back());
        pos[p].pop_back();

        sum += (v[i] < 0);


        ans += sum ;

    }


	return ans;
}

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