Submission #975595

#	Time	Username	Problem	Language	Result	Execution time	Memory
975595		attky	Arranging Shoes (IOI19_shoes)	C++17	Compilation error	0 ms	0 KiB

shoes

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdint>

using namespace std;

struct Pair {
    int gauche, droite, nb;
    void nbDeplacement() {
        nb = gauche + droite;
    }
    bool operator< (Pair other) {
        return nb < other.nb;
    }
};

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_swap(vector<int> S) {
    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]});
        }
    }
    for(int loop = 0; loop < n; ++loop) {
        pair[loop].nbDeplacement();
    }
    sort(pair.begin(), pair.end());
    long long int nbDeplacement = 0;
    for(int loop = 0; loop < n; ++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_swap(std::vector<int>)':
shoes.cpp:61:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for(int loop = 0; loop < S.size(); ++loop) {
      |                       ~~~~~^~~~~~~~~~
shoes.cpp:71:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         for(int looping = 0; looping < shoeLeft[loop].size(); ++looping) {
      |                              ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccR8Oack.o: in function `main':
grader.cpp:(.text.startup+0x2a8): undefined reference to `count_swaps(std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status