oj.uz

Submission #975602

# Submission time Handle Problem Language Result Execution time Memory
975602 2024-05-05T14:22:09 Z attky Arranging Shoes (IOI19_shoes) C++17
10 / 100
 0 ms 348 KB 
#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_swaps(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

shoes.cpp: In function 'int64_t count_swaps(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) {
      |                              ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -