Submission #584058

#	Time	Username	Problem	Language	Result	Execution time	Memory
584058		snokes	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	204 ms	16180 KiB

shoes

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

#ifdef LOCAL
void print() {cerr << ']' << endl;}
template<typename Head, typename... Tail> void print(Head H, Tail... T) {cerr << ' ' << H; if(sizeof...(T)) cerr << ','; print(T...); }
template<typename T> ostream& operator << (ostream& os, vector<T> v){os << "["; bool first = 1; for(auto x : v) {if(!first) os << ", "; os << x; first = 0;} os << "]"; return os;}
template<typename A, typename B> ostream& operator <<(ostream& os,pair<A, B> p) {return os << "(" << p.first << ", " << p.second << ")"; return os;}
template<typename A, typename B, typename C> ostream& operator << (ostream& os, tuple<A, B, C> a) {os << '(' << get<0>(a) << ", " << get<1>(a) << ", " << get<2>(a) << ")"; return os;}
template<typename A, size_t S> ostream& operator << (ostream& os, array<A, S> a) {os << "["; bool first = 1; for(auto x : a) {if(!first) os << ", "; os << x; first = 0;} os << "]"; return os;}
template<typename A> ostream& operator << (ostream& os, set<A> s) {os << "["; bool first = 1; for(auto x : s) {if(!first) os << ", "; os << x; first = 0;} os << "]"; return os;}
template<typename A, typename B> ostream& operator << (ostream& os, map<A, B> m) {os << "["; bool first = 1; for(auto x : m) {if(!first) os << ", "; os << x; first = 0;} os << "]"; return os;}
#define dbg(...) cerr << '[' << #__VA_ARGS__ << ":", print(__VA_ARGS__);
#else
#define dbg(...)
#endif // LOCAL

#define ll long long
#define vt vector
#define pb push_back
#define sz(x) int((x).size())

const int INF = 1e9 + 5;

struct SegTree
{
    vt<int> S;
    int N;
    SegTree(int _N)
    {
        N = 1;
        while(N < _N) N *= 2;
        S = vt<int>(2 * N);
    }

    int qry(int idx, int l, int r, int i)
    {
        if(l == r) return S[i];
        int m = (l + r) / 2;
        if(idx <= m) return S[i] + qry(idx, l, m, 2 * i);
        else return S[i] + qry(idx, m + 1, r, 2 * i + 1);
    }

    int operator [] (int idx) {return qry(idx, 1, N, 1);}

    void rangeAdd(int l, int r, int x, int a, int b, int i)
    {
        if(l <= a && b <= r)
        {
            S[i] += x;
            return;
        }
        if(r < a || b < l) return;
        int m = (a + b) / 2;
        rangeAdd(l, r, x, a, m, 2 * i);
        rangeAdd(l, r, x, m + 1, b, 2 * i + 1);
    }

    void rangeAdd(int l, int r, int x) {rangeAdd(l, r, x, 1, N, 1);}
};


long long count_swaps(vector<int> A)
{
    int N = A.size();
    assert(N % 2 == 0);
    N /= 2;
    vt<vt<int>> rPos(N + 1), lPos(N + 1);

    for(int i = 0; i < 2 * N; i++)
    {
        if(A[i] < 0) lPos[-A[i]].pb(i);
        else rPos[A[i]].pb(i);
    }

    for(int i = 1; i <= N; i++) reverse(rPos[i].begin(), rPos[i].end());
    for(int i = 1; i <= N; i++) reverse(lPos[i].begin(), lPos[i].end());

    int64_t ans = 0;

    SegTree s(2 * N);
    for(int i = 1; i <= 2 * N; i++) s.rangeAdd(i, i, i);

    for(int i = 0; i < 2 * N; i++)
    {
        if(s[i + 1] >= INF) continue;
        int val = abs(A[i]);
        int myPos = lPos[val].back(), oPos = rPos[val].back();
        lPos[val].pop_back();
        rPos[val].pop_back();
        if(A[i] > 0)
        {
            swap(myPos, oPos);
            ++ans;
        }
        assert(s[oPos + 1] > s[myPos + 1]);
        ans += s[oPos + 1] - s[myPos + 1] - 1;
        s.rangeAdd(myPos + 2, oPos, +1);
        s.rangeAdd(myPos + 1, myPos + 1, INF);
        s.rangeAdd(oPos + 1, oPos + 1, INF);
    }
    return ans;
}

/*
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N;
    cin >> N;
    vt<int> A(N);
    for(int i = 0; i < N; i++) cin >> A[i];
    count_swaps(A);
}
*/

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