Submission #824191

#	Time	Username	Problem	Language	Result	Execution time	Memory
824191		SoulKnight	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	198 ms	29964 KiB

shoes

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

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

const ll N = 3e5 + 5;
const ll LG = 20;
const ll INF = 2e9 + 5;
const ll MOD = 998244353;



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


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

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

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

ll move(vector<ll>& v){
    ll x = v.size();
    ll ans = 0LL;
    for (ll 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 (ll 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 (ll i = 0; i < p.second.size(); i++) vec.push_back({p.second[i], mp[-p.first][i]});
    }
    sort(vec.begin(), vec.end(), [&](const pair<ll, ll>& x, const pair<ll, ll>& y){
        return min(x.first, x.second) < min(y.first, y.second);
    });
    // sort(vec.begin(), vec.end());

    t.resize(n);
    for (ll 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:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for (ll 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: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15