Submission #476918

#	Time	Username	Problem	Language	Result	Execution time	Memory
476918		ponytail	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	329 ms	78016 KiB

shoes

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
typedef long long ll;
mt19937 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());

int bit[2 * MAXN];
void add(int x, int v) {
    for(;x<2 * MAXN;x+=x&-x) bit[x] += v;
}
int sum(int x) {
    int s= 0;
    for(;x;x-=x&-x) s += bit[x];
    return s;
}
ll count_swaps(vector<int> S) {
    for(int i=0; i<2 * MAXN; i++) bit[i] = 0;
    ll ans = 0;
    map<int, queue<int> >mp;
    for(int i=0; i<S.size(); i++) {
        if(S[i] < 0) {
            mp[-S[i]].push(i);
        }
    }
    int partner[S.size()];
    for(int i=0; i<S.size(); i++) {
        if(S[i] > 0) {
            partner[i] = mp[S[i]].front();
            partner[mp[S[i]].front()] = i;
            mp[S[i]].pop();
        }
    }
    vector<pair<int, int> > v;
    for(int i=0; i<S.size(); i++) {
        if(S[i] > 0) {
            if(partner[i] > i) {
                v.push_back({partner[i] + i, i});
            }
            else {
                v.push_back({partner[i] + i - 1, i});
            }
        }
    }
    sort(v.begin(), v.end());
    int lb = 0;
    for(pair<int, int> x: v) {
        int me = x.second + sum(2 * MAXN - 1) - sum(x.second + 1);
        int pe = partner[x.second] + sum(2 * MAXN - 1) - sum(partner[x.second] + 1);
        ans += (partner[x.second] > x.second ? me + pe : me + pe - 1) - 2 * lb;
        lb += 2;
        add(x.second + 1, 1);
        add(partner[x.second] + 1, 1);
    }
    return ans;
}

Compilation message (stderr)

shoes.cpp: In function 'll count_swaps(std::vector<int>)':
shoes.cpp:20:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for(int i=0; i<S.size(); i++) {
      |                  ~^~~~~~~~~
shoes.cpp:26:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for(int i=0; i<S.size(); i++) {
      |                  ~^~~~~~~~~
shoes.cpp:34:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for(int i=0; i<S.size(); i++) {
      |                  ~^~~~~~~~~

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