Submission #850887

#	Time	Username	Problem	Language	Result	Execution time	Memory
850887		Pekiban	Arranging Shoes (IOI19_shoes)	C++17	50 / 100	38 ms	26712 KiB

shoes

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

using namespace std;
const int mxN = 1e5+2;
int bit[mxN];

void add(int idx) {
    for (; idx < mxN; idx |= (idx + 1)) bit[idx]++;
}
int sum(int idx) {
    int sum = 0;
    for (; idx >= 0; idx = ((idx) & (idx+1))-1)   sum+=bit[idx];
    return sum;
}
long long count_swaps(vector<int> s) {
    long long ans = 0; const int n = s.size();
    vector<bool> p(mxN, 0);
    vector<int> pos[mxN], neg[mxN], ind(mxN, 0);
    for (int i = 0; i < n; ++i) {
        if (s[i] > 0) {
            pos[s[i]].push_back(i);
        }
        else {
            neg[-s[i]].push_back(i);
        }
    }
    
    for (int i = 1; i <= n; ++i) {
        sort(pos[i].begin(), pos[i].end());
        sort(neg[i].begin(), neg[i].end());
    }
    int idx = 0;
    while (idx < n) {
        if (p[idx]) {
            idx++;
            continue;
        }
        // cout << idx << '\n';
        // for (int i = 0; i < n; ++i) {
        //     cout << p[i] << '\n';
        // } 
        // cout << "=n\n";
        if (s[idx] < 0) {
            ans += pos[-s[idx]][ind[-s[idx]]] - idx - 1 - (sum(pos[-s[idx]][ind[-s[idx]]]) - sum(idx));
            // cout << pos[-s[idx]][ind[-s[idx]]] - idx - 1 - (sum(pos[-s[idx]][ind[-s[idx]]]) - sum(idx)) << ' ';
            p[pos[-s[idx]][ind[-s[idx]]]] = 1;
            add(pos[-s[idx]][ind[-s[idx]]]);
            ind[-s[idx]]++;
        }
        else {
            ans += neg[s[idx]][ind[s[idx]]] - idx - (sum(neg[s[idx]][ind[s[idx]]])-sum(idx));
            // cout << neg[s[idx]][ind[s[idx]]] - idx - 1 - (sum(neg[s[idx]][ind[s[idx]]])-sum(idx)) << ' ';
            p[neg[s[idx]][ind[s[idx]]]] = 1;
            add(neg[s[idx]][ind[s[idx]]]);
            ind[s[idx]]++;
        }
        idx++;
    }
    return ans;
}

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