Submission #824189

#	Time	Username	Problem	Language	Result	Execution time	Memory
824189		SoulKnight	Arranging Shoes (IOI19_shoes)	C++17	50 / 100	136 ms	51548 KiB

shoes

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

#define ll long long
#define ln '\n'

const int N = 1e5 + 5;
const int LG = 20;
const int INF = 2e9 + 5;
const int MOD = 998244353;



vector<int> s, t;
int n, ft[N];
map<int, vector<int>> mp;
vector<pair<int, int>> vec;


void update(int p, int delta){
    for (++p; p < N; p += (p & -p)) ft[p] += delta;
}

int sum(int p){
    int res = 0;
    for (++p; p > 0; p -= (p & -p)) res += ft[p];
    return res;
}

void init(){
    cin >> n;
    s.resize(2*n);
    for (int i = 0; i < 2*n; i++) cin >> s[i];
}

ll move(vector<int>& v){
    int x = v.size();
    ll ans = 0LL;
    for (int i = 0; i < x; i++){
        ans += v[i] - sum(v[i]);
        update(v[i]+1, 1);
    }
    return ans;
}

ll solve(vector<int>& s){
    n = s.size();
    for (int i = 0; i < n; i++) mp[s[i]].push_back(i);

    for (auto& p: mp){
        if (p.first > 0) break;
        sort(p.second.begin(), p.second.end());
        sort(mp[-p.first].begin(), mp[-p.first].end());

        for (int i = 0; i < p.second.size(); i++) vec.push_back({p.second[i], mp[-p.first][i]});
    }
    sort(vec.begin(), vec.end(), [&](const pair<int, int>& x, const pair<int, int>& y){
        return min(x.first, x.second) < min(y.first, y.second);
    });
    // sort(vec.begin(), vec.end());

    t.resize(n);
    for (int i = 0; i < n; i+=2) {t[i] = vec[i/2].first; t[i+1] = vec[i/2].second;}
    // for (auto& u: t) cout << u << ' ';
    // cout << ln;
    return move(t);
    // t = {1,3,2,0};
    // return move(t);

}



long long count_swaps(std::vector<int> s) {
	return solve(s);
}

Compilation message (stderr)

shoes.cpp: In function 'long long int solve(std::vector<int>&)':
shoes.cpp:56:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for (int i = 0; i < p.second.size(); i++) vec.push_back({p.second[i], mp[-p.first][i]});
      |                         ~~^~~~~~~~~~~~~~~~~

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