Submission #975662

#	Time	Username	Problem	Language	Result	Execution time	Memory
975662		attky	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	79 ms	21460 KiB

shoes

#include <bits/stdc++.h>
 
using namespace std;
 
struct Pair {
    int gauche, droite;
    bool operator< (Pair other) {
        return min(gauche, droite) < min(other.gauche, other.droite);
    }
};
 
int segtree[524288], tailleIntervalle[524288][2];
 
void define() {
    for(int loop = 0; loop < 262144; ++loop) {
        tailleIntervalle[loop+262144][0] = loop+1;
        tailleIntervalle[loop+262144][1] = loop+1;
    }
    for(int loop = 262143; loop >= 1; --loop) {
        tailleIntervalle[loop][0] = tailleIntervalle[loop*2][0];
        tailleIntervalle[loop][1] = tailleIntervalle[loop*2+1][1];
    }
    for(int loop = 1; loop < 524288; ++loop) {
        segtree[loop] = 0;
    }
}
 
void add(int debut, int pos) {
    if(tailleIntervalle[pos][0] >= debut) {
        segtree[pos]++;
    }
    else {
        int gauche = 2*pos, droite = 2*pos+1;
        if(tailleIntervalle[gauche][1] >= debut) {
            add(debut, gauche);
        }
        if(tailleIntervalle[droite][1] >= debut) {
            add(debut, droite);
        }
    }
}
 
int number(int pos) {
    int nombre = segtree[pos];
    if(pos > 1) {
        nombre += number(pos/2);
    }
    return nombre;
}
 
int64_t count_swaps(vector<int> S) {
    define();
    int n = S.size()/2;
    vector<vector<int>> shoeLeft(n);
    vector<vector<int>> shoeRight(n);
    for(int loop = 0; loop < S.size(); ++loop) {
        if(S[loop] > 0) {
            shoeRight[S[loop]-1].push_back(loop);
        }
        else {
            shoeLeft[-(S[loop])-1].push_back(loop);
        }
    }
    vector<Pair> pair;
    for(int loop = 0; loop < n; ++loop) {
        for(int looping = 0; looping < shoeLeft[loop].size(); ++looping) {
            pair.push_back({shoeLeft[loop][looping], shoeRight[loop][looping]});
        }
    }
    sort(pair.begin(), pair.end());
    long long int nbDeplacement = 0;
    for(int loop = 0; loop < pair.size(); ++loop) {
        int g = pair[loop].gauche, d = pair[loop].droite;
        int change = -1;
        if(d < g) {
            change++;
        }
        int ng = max(0, g-number(g+262144));
        int nd = max(0, d-number(d+262144));
        add(g+1, 1);
        add(d+1, 1);
        nbDeplacement += ng + nd + change;
    }
    return nbDeplacement;
}

Compilation message (stderr)

shoes.cpp: In function 'int64_t count_swaps(std::vector<int>)':
shoes.cpp:56:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for(int loop = 0; loop < S.size(); ++loop) {
      |                       ~~~~~^~~~~~~~~~
shoes.cpp:66:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         for(int looping = 0; looping < shoeLeft[loop].size(); ++looping) {
      |                              ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
shoes.cpp:72:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Pair>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for(int loop = 0; loop < pair.size(); ++loop) {
      |                       ~~~~~^~~~~~~~~~~~~

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