Submission #476880

#	Time	Username	Problem	Language	Result	Execution time	Memory
476880		JovanB	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	156 ms	139344 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;

const int N = 200000;

int bit[N+5];

void bit_add(int x){
    while(x <= N){
        bit[x]++;
        x += x & -x;
    }
}

int bit_get(int x){
    int res = 0;
    while(x){
        res += bit[x];
        x -= x & -x;
    }
    return res;
}

deque <int> ima[N+5];
int tren[N+5];

long long count_swaps(std::vector<int> vec) {
    ll res = 0;
    int tr = 0;
    for(int i=1; i<=N; i++) tren[i] = -1;
	for(int i=0; i<vec.size(); i++){
        int x = vec[i];
        bool left = 0;
        if(x < 0) left = 1, x = -x;
        if(ima[x].size() && tren[x] != left){
            int g = ima[x].front();
            ima[x].pop_front();
            res += bit_get(N) - bit_get(g);
            bit_add(g);
            res += left;
        }
        else{
            ima[x].push_back(++tr);
            tren[x] = left;
            bit_add(tr);
        }

	}
	return res;
}

Compilation message (stderr)

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