Submission #533244

#	Time	Username	Problem	Language	Result	Execution time	Memory
533244		andecaandeci	Arranging Shoes (IOI19_shoes)	C++17	50 / 100	99 ms	22736 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
using namespace std;

vector<int> kiri[200005], kanan[200005];
vector<pair<int,int> > swaps;
int tree[4 * 200005];

void upd(int idx, int l, int r, int titik, int val){
    if(titik > r || titik < l){
        return;
    }

    if(l == r){
        tree[idx] += val;
        return;
    }

    upd(2 * idx, l, (l + r)/2, titik, val);
    upd(2 * idx + 1, (l + r)/2 + 1, r, titik, val);
    tree[idx] = tree[2 * idx] + tree[2 * idx + 1];
}

int cari(int idx, int l, int r, int kiri, int kanan){
    if(kiri > r || kanan < l){
        return 0;
    }

    if(l >= kiri && r <= kanan){
        return tree[idx];
    }

    int satu = cari(2 * idx, l, (l + r)/2, kiri, kanan);
    int dua = cari(2 * idx + 1, (l + r)/2 + 1, r, kiri, kanan);
    return satu + dua;
}

long long count_swaps(vector<int> s) {
    int n = s.size() / 2;
    for(int i = 0; i < s.size(); i++){
        if(s[i] < 0){
            kiri[-s[i]].pb(i + 1);
        }else{
            kanan[s[i]].pb(i + 1);
        }    
    }

    int ans = 0;
    for(int i = 1; i < s.size() + 5; i++){
        for(int j = 0; j < kiri[i].size(); j++){
            int lef = kiri[i][j];
            int rig = kanan[i][j];
            if(lef > rig){
                ans++;
                swap(lef, rig);
            }
            // cout << lef << " " << rig << " here\n";
            swaps.pb(mp(lef, rig));
        }
    }

    sort(swaps.begin(), swaps.end());
    memset(tree, 0, sizeof(tree));
    for(int i = 0; i < swaps.size(); i++){
        int l = swaps[i].first;
        int r = swaps[i].second;
        long long ans_now = (r - l - 1) - cari(1, 1, 200000, l, r);
        ans += ans_now;
        upd(1, 1, 200000, l, 1);
        upd(1, 1, 200000, r, 1);
    }
    return ans;
}

// int main(){
//     int n; cin >> n;
//     vector<int> bawa;
//     for(int i = 0; i < n; i++){
//         int x; cin >> x;
//         bawa.pb(x);
//     }
//     cout << count_swaps(bawa) << "\n";
// }

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:44:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for(int i = 0; i < s.size(); i++){
      |                    ~~^~~~~~~~~~
shoes.cpp:53:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(int i = 1; i < s.size() + 5; i++){
      |                    ~~^~~~~~~~~~~~~~
shoes.cpp:54:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         for(int j = 0; j < kiri[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~~~~
shoes.cpp:68:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for(int i = 0; i < swaps.size(); i++){
      |                    ~~^~~~~~~~~~~~~~
shoes.cpp:43:9: warning: unused variable 'n' [-Wunused-variable]
   43 |     int n = s.size() / 2;
      |         ^

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