제출 #143761

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
143761		dacin21	Arranging Shoes (IOI19_shoes)	C++17	50 / 100	1047 ms	2680 KiB

shoes

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

using ll = long long;
using ull = unsigned long long;
using fl = long double;
template<typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename S, typename T>
void xmin(S&a, T const&b){if(b<a) a=b;}
template<typename S, typename T>
void xmax(S&a, T const&b){if(b>a) a=b;}

template<bool enabled>
struct Debug{
    template<typename S, typename T = void> struct Tag_Printable : false_type {};
    template<typename S> struct Tag_Printable<S, decltype((void)(cerr << declval<S>()))> : true_type {};
    template<typename S, typename T = void> struct Tag_Iterable: false_type {};
    template<typename S> struct Tag_Iterable<S, decltype((void)(begin(declval<S>()), end(declval<S>())))> : true_type {};
    template<typename T, typename... Args>
    Debug& print(T const&x, true_type, Args...){
        #ifdef LOCAL_RUN
        if(enabled){
            cerr << boolalpha << x;
        }
        #endif // LOCAL_RUN
        return *this;
    }
    template<typename T>
    Debug& print(T const&x, false_type, true_type){
        *this << "[";
        bool first = true;
        for(auto &e:x){
            if(!first) *this << ", ";
            *this << e;
            first = false;
        }
        return *this << "]";
    }
    template<typename S, typename T>
    Debug& print(pair<S, T> const&x, false_type, false_type){
        return *this << "(" << x.first << ", " << x.second << ")";
    }
    template<typename T>
    Debug& operator<<(T const&x){
        return print(x, Tag_Printable<T>{}, Tag_Iterable<T>{});
    }
};
 Debug<true> debug;
// Debug<false> debug; // disable debug printing
#define named(x) string(#x) << " : " <<  x

constexpr int inf = 1e9;

long long count_swaps(std::vector<int> v) {
    const int n = v.size()/2;
    ll ret = 0;
    for(int i=0;i<n;++i){
        const int l = 2*i;
        vector<pair<int, int> > occ(n+1, {inf, inf});
        for(int j=l;j<2*n;++j){
            if(v[j] < 0) xmin(occ[-v[j]].second, j);
            else xmin(occ[v[j]].first, j);
        }
        debug << l << " " << named(occ) << "\n";
        debug << v << "\n";
        const int a = min_element(occ.begin(), occ.end(), [](auto const&a, auto const&b){return a.first+a.second < b.first+b.second;}) - occ.begin();
        debug << "best: " << a << " : " << occ[a].first << " " << occ[a].second << "\n";

        {
        auto it = find(v.begin()+l, v.end(), -a);
        ret+=it - (v.begin()+l);
        rotate(v.begin()+l, it, it+1);
        }
        {
        auto it = find(v.begin()+l+1, v.end(), a);
        ret+=it - (v.begin()+l+1);
        rotate(v.begin()+l+1, it, it+1);
        }
    }
    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