Submission #695270

#	Time	Username	Problem	Language	Result	Execution time	Memory
695270		allin27x	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	480 ms	27396 KiB

shoes

#include <bits/stdc++.h>
using namespace std;

long long count_swaps(vector<int> S){
    long long res = 0;
    int n = S.size();
    long long t = 0;
    unordered_map<int, set<int>> f;
    vector<pair<int, int>> pairs(n/2);
    int r = n/2-1;
    for (int i=n-1; i>=0; i--){
        if (!f[S[i]].size()){
            f[-S[i]].insert(-i);
        } else {
            int p = -*(f[S[i]].lower_bound(-(int)1e6));
            pairs[r] = make_pair(i,p); r--;
            if (S[i]<0) res+=p-i-1; else res+=p-i;
            f[S[i]].erase(-p);
        }
    }
    deque<int> sp;
    for (int i=0; i<n/2; i++){
        int MIN = pairs[i].first;
        int MAX = pairs[i].second;
        if (sp.size()==0){
            sp.push_front(MAX); continue;
        }
        int min_a = 0; int min_b = sp.size()-1;
        while (min_a<min_b){
            int m = (min_a + min_b)/2;
            if (sp[m]>=MIN) min_b = m;
            else min_a = m+1;
        }
        int max_a = 0; int max_b = sp.size()-1;
        while (max_a<max_b){
            int m = (max_a + max_b +1)/2;
            if (sp[m]>MAX) max_b = m-1;
            else max_a = m;
        }
        if (sp[0]>MAX){
            sp.push_front(MAX);
            continue;
        }
        sp.insert(sp.begin()+max_a+1, MAX);
        if (sp[min_a]<MIN) continue;
        t+=max(max_a-min_a+1,0);
    }

    res-=t;



    return res;
}

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