Submission #1070689

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070689		kiethm07	Arranging Shoes (IOI19_shoes)	C++14	50 / 100	20 ms	13184 KiB

shoes

#include <bits/stdc++.h>

#define pii pair<int,int>
#define iii pair<int,pii>
#define fi first
#define se second

#define vi vector<int>
#define vii vector<pii>
#define pb(i) push_back(i)
#define all(x) x.begin(),x.end()

#define TEXT "a"

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const int inf = 1e9 + 7;
const ld eps = 1e-8;
const double pi = acos(-1);
const int N = 1e5 + 5;

class BIT{
private:
    vector<int> bit;
    int n;
public:
    BIT(int m){
        n = m;
        bit.resize(n + 5,0);
    }
    void update(int i,int v){
        while(i <= n){
            bit[i] += v;
            i += i & (-i);
        }
    }
    int get(int i){
        int res = 0;
        while(i > 0){
            res += bit[i];
            i -= i & (-i);
        }
        return res;
    }
};

vector<int> c[N][2];

ll count_swaps(vector<int> a){
    int n = a.size();
    ll res = 0;
    vector<bool> mark(n + 5,0);
    for (int i = 0; i < n; i++){
        c[i][0].clear();
        c[i][1].clear();
    }
    for (int i = 0; i < n; i++){
        bool f = a[i] > 0;
        int t = abs(a[i]);
        c[t][f].push_back(i + 1);
    }
    for (int i = 1; i <= n; i++){
        reverse(all(c[i][0]));
        reverse(all(c[i][1]));
    }
    BIT bit(n);
    for (int i = 0; i < n; i++){
        if (mark[i]) continue;
        mark[i] = 1;
        bool f = a[i] > 0;
        int t = abs(a[i]);
        int pre = c[t][1 ^ f].back();
        c[t][1 ^ f].pop_back();
        c[t][f].pop_back();
        mark[pre - 1] = 1;
        int id = pre - bit.get(pre) - 1;
        res += id - 1 + f;
        //cout << i << " " << id << " " << pre << " " << bit.get(pre) << " " << res << "\n";
        bit.update(pre,1);
        bit.update(i + 1,1);
    }
    return res;
}

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