Submission #474250

#	Time	Username	Problem	Language	Result	Execution time	Memory
474250		aris12345678	Arranging Shoes (IOI19_shoes)	C++14	45 / 100	38 ms	4928 KiB

shoes

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

const int mxN = 2*100005;
int bit[mxN];

void upd(int pos, int n) {
    while(pos <= n) {
        bit[pos]++;
        pos += (pos&(-pos));
    }
}

int ask(int pos) {
    int ans = 0;
    while(pos > 0) {
        ans += bit[pos];
        pos -= (pos&(-pos));
    }
    return ans;
}

long long count_swaps(vector<int> s) {
    int n = s.size();
    long long ans = 0;
    vector<int> neg, pos;
    for(int i = 0; i < n; i++) {
        if(s[i] > 0)
            pos.push_back(i+1);
        else
            neg.push_back(i+1);
    }
    int m = int(neg.size());
    for(int i = 0; i < m; i++) {
        if(neg[i] > pos[i]) {
            ans += ((neg[i]-pos[i])-(ask(neg[i])-ask(pos[i]-1)));
            // cout << neg[i]-pos[i] << " " << i << " " << ans << " " << neg[i] << " " << pos[i] << " " << ask(neg[i])-ask(pos[i]-1) << "\n";
            upd(neg[i], n);
        } else {
            ans += ((pos[i]-neg[i]-1)-(ask(pos[i])-ask(neg[i]-1)));
            // cout << i << " " << ans << " " << neg[i] << " " << pos[i] << " " << ask(pos[i])-ask(neg[i]-1) << "\n";
            upd(pos[i], n);
        }
    }
    return ans;
}

// int main() {
//     int n;
//     scanf("%d", &n);
//     vector<int> s(n);
//     for(int i = 0; i < n; i++)
//         scanf("%d", &s[i]);
//     printf("%lld\n", count_swaps(s));
//     return 0;
// }

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