Submission #1177487

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177487		Boycl07	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	114 ms	138568 KiB

shoes

#include "shoes.h"
#include "bits/stdc++.h"

using namespace std;

#define ll long long
#define rep(i, n) for(int i = 1; i <= (n); ++i)
#define forn(i, l, r) for(int i = (l); (i) <= (r); ++i)
#define ford(i, r, l) for(int i = (r); (i) >= (l); --i)
#define endl "\n"
#define fi first
#define se second
#define pb push_back
#define pll pair<ll, ll>
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
#define sz(a) (int)(a.size())
#define task "note"

template<typename T> bool maximize(T &res, const T &val) {if(res < val) {res = val; return 1;} return 0;}
template<typename T> bool minimize(T &res, const T &val) {if(res < val) return 0; res = val; return 1;}
inline int readInt()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();int n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline ll readLong()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();ll  n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline string readString() {char c;while(c=getchar(),c==' '||c=='\n'||c=='\t');string s({c});while(c=getchar(),c!=EOF&&c!=' '&&c!='\n'&&c!='\t')s+=c;return s;}

const int N = 2e5 + 3;
const int LOG = 20;
const int LIM = 1e6 + 3;

int n;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
double get_cur_time() {return chrono::steady_clock::now().time_since_epoch().count();}
queue<int> q[N];

struct fenwick_tree
{
    int bit[N];
    void update(int u, int v)
    {
        for(; u <= 2 * n; u += u & -u) bit[u] += v;
    }
    int get(int u)
    {
        int res = 0;
        for(; u; u -= u & -u) res += bit[u];
        return res;
    }
} BIT;

ll count_swaps(vector<int> S)
{
    n = sz(S) / 2;
    vector<int> b(S);
    for(int i = sz(S) - 1, cur = n - 1; i >= 0; --i)
    {
        int x = S[i];
        if(sz(q[-x + n]))
        {
            int j = q[-x + n].front(); q[-x + n].pop();
            b[i] = (cur << 1) + (x > 0);
            b[j] = (cur << 1) + (x < 0);
            --cur;
        }
        else q[x + n].push(i);
    }
    ll res = 0;
//    for(int i = 0; i < sz(S); ++i)
//    {
//        cout << b[i] << " ";
//    }
//    cout << endl;
    for(int i = sz(S) - 1; i >= 0; --i)
    {
        int x = b[i];
        res += BIT.get(x + 1);
        BIT.update(x + 1, 1);
    }
    return res;
}

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