Submission #1242752

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242752		superomego	Arranging Shoes (IOI19_shoes)	C++20	45 / 100	108 ms	31416 KiB

shoes

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

long long count_swaps(vector<int> S){
    
    long long n = S.size(), ret = 0;
    vector<long long> dp(n, 0);
    vector<long long> pref(1, 0);
    
    unordered_map<int, pair<vector<long long>, vector<long long>>> v;
    set<tuple<long long, long long, long long>> s;
    
    set<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({(*it1), (*it2), 0});
            else s.insert({(*it2), (*it1), -1});
            it1++; it2++;
            
        }
        
    }
    
    for(auto &[j, i, _] : s){
        dp[i]++;
    }
    
    for(auto i : dp){
        pref.push_back(pref.back() + i);
    }
    
    for(auto it = s.rbegin(); it != s.rend(); ++it){
        
        if(ts.empty()){
            ret += get<0>(*it) + get<2>(*it) - get<1>(*it);
            ts.insert(get<1>(*it));
        }
        else{
            long long val = pref[get<0>(*it)+1] - pref[get<1>(*it)+1];
            ret += get<0>(*it) + get<2>(*it) - get<1>(*it) - val;
            ts.insert(get<1>(*it));
        }
    }
    
    return ret;
   
}

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