oj.uz

Submission #143765

# Submission time Handle Problem Language Result Execution time Memory
143765 2019-08-15T03:50:31 Z dacin21 Arranging Shoes (IOI19_shoes) C++17
10 / 100
 2 ms 376 KB 
#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;

template<typename T>
T iabs(T const&a){
    return max(a, -a);
}

long long count_swaps(std::vector<int> v) {
    const int n = v.size()/2;
    ll ret = 0;
    vector<vector<int> > occs(n+1);
    vector<pair<int, int> > ps;
    for(int i=0;i<2*n;++i){
        const int a = v[i];
        const int aa = iabs(a);
        if(occs[aa].empty() || v[occs[aa].back()] == a){
            occs[aa].push_back(i);
        } else {
            const int j = occs[aa].back();
            occs[aa].pop_back();
            if(a<0) ps.emplace_back(i, j);
            else ps.emplace_back(j, i);
        }
    }
    assert((int)ps.size() == n);
    sort(ps.begin(), ps.end(), [](auto const&a, auto const&b){return a.first+a.second < b.first+b.second;});
    debug << ps << "\n";
    for(int i=0;i<n;++i){
        const int l = 2*i;
        auto const&e = ps[i];
        debug << e << " " << l << " : " << e.first-l << " " << e.second-l-1 << "\n";
        ret += iabs(e.first-l) + iabs(e.second-l-1);
        debug << ret << "\n";
    }
    return ret/2;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 252 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 252 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Incorrect 2 ms 256 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 252 KB Output is correct
3 Incorrect 2 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Incorrect 2 ms 256 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 252 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Incorrect 2 ms 256 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 252 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Incorrect 2 ms 256 KB Output isn't correct
5 Halted 0 ms 0 KB -