Submission #1242681

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242681		superomego	Arranging Shoes (IOI19_shoes)	C++20	50 / 100	1095 ms	25000 KiB

shoes

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

long long count_swaps(vector<int> S){
    
    long long n = S.size(), ret = 0;
    map<int, pair<vector<long long>, vector<long long>>> v;
    
    set<tuple<long long, long long, long long>> s;
    set<pair<long long, long long>> ts;
    
    for(int i = 0; i < S.size(); ++i){
        
        if(v.find(abs(S[i])) == v.end()) v[abs(S[i])] = {vector<long long>(), vector<long long>()};
        
        if(S[i] < 0) v[-S[i]].first.push_back(i);
        else v[S[i]].second.push_back(i);
    }
    for(auto &[k, w] : v){
        
        auto it1 = w.first.rbegin(), it2 = w.second.rbegin();
        while(it1 != w.first.rend()){
            
            if((*it1) > (*it2)) s.insert({(*it2), (*it1), 0});
            else s.insert({(*it1), (*it2), -1});
            it1++; it2++;
            
        }
        
    }
    
    for(auto it = s.rbegin(); it != s.rend(); ++it){
        
        if(ts.empty()){
            ret += get<1>(*it) + get<2>(*it) - get<0>(*it);
            ts.insert({get<1>(*it) + get<2>(*it), get<0>(*it)});
        }
        else{
            
            long long val = 0;
            for(auto i : ts) if((i.first > get<1>(*it) - 1) && (i.second < get<1>(*it))) val++; 

            ret += get<1>(*it) + get<2>(*it) - get<0>(*it) - val;
            ts.insert({get<1>(*it) + get<2>(*it), get<0>(*it)});
        }
        
    }
    
    return ret;
   
}

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