제출 #1242707

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1242707		superomego	Arranging Shoes (IOI19_shoes)	C++20	50 / 100	1096 ms	24672 KiB

shoes

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

long long count_swaps(vector<int> S){
    
    long long n = S.size(), ret = 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 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 = distance(ts.lower_bound(get<1>(*it)), ts.upper_bound(get<0>(*it)));
            ret += get<0>(*it) + get<2>(*it) - get<1>(*it) - val;
            ts.insert(get<1>(*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