Submission #386170

#	Time	Username	Problem	Language	Result	Execution time	Memory
386170		Christopher_Rdz	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	547 ms	148204 KiB

shoes

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

void mapear(vector<int> &s){
    int contador = 0;
    map<long long int,queue<long long int> > mapa;
    for(auto &x: s){
        if(!mapa[-x].empty()){
            int indice = x;
            x =- mapa[-x].front();
            mapa[-indice].pop();
        }else{
            int valor = (x > 0) ? ++contador : -1 *(++contador);
            mapa[x].push(valor);
            x = valor;
        }
    }
}

long long int bit[400002];

long long int query(int indice){
    long long int suma=0;
    while(indice > 0){
        suma += bit[indice];
        indice -= (indice & (-indice));
    }
    return suma;
}

long long int query_2(int l,int r){
    return(query(r) - query(l - 1));
}

void update(int i, int valor, int n){
    while(i <= n){
        bit[i] += (long long int)valor;
        i += (i & (-i));
    }
}

long long count_swaps(vector<int> s) {
    long long int movs=0;
    mapear(s); 
    int n = s.size()+1;
    for(int i = 0;i <s.size(); i++){
    if(s[i] > 0 and query_2(abs(s[i]), abs(s[i])) == 0){
        movs++;
    }
    movs += query_2(abs(s[i]) + 1, n);
    update(abs(s[i]), 1, n);
  }
    return movs;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:47:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for(int i = 0;i <s.size(); 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