#include "shoes.h" #include <iostream> #include <vector> using namespace std; long long count_swaps(vector<int> S) { int n = S.size()/2; long long res = 0; vector<int> left[n+1], right[n+1]; vector<int> othershoe(2*n, -1); for(int i = 0; i < 2*n; i++) { if(S[i] < 0) left[-S[i]].push_back(i); else right[S[i]].push_back(i); } for(int i = 1; i <= n; i++) { for(int j = 0; j < left[i].size(); j++) { if(left[i][j] < right[i][j]) othershoe[left[i][j]] = right[i][j]; else { othershoe[right[i][j]] = left[i][j]; res++; } } } /*for(int i = 1; i <= n; i++) { for(int j: left[i]) cout << j << ' '; cout << '\n'; for(int j: right[i]) cout << j << ' '; cout << "\n\n"; }*/ vector<int> rightshift(2*n, 0); for(int i = 0; i < 2*n; i++) { if(othershoe[i] == -1) continue; res += othershoe[i] - i + 1; for(int j = i; j >= 1; j -= j&-j) res -= rightshift[j]; for(int j = othershoe[i]; j >= 1; j -= j&-j) res += rightshift[j]; for(int j = i+1; j < 2*n; j += j&-j) rightshift[j]++; for(int j = othershoe[i]+1; j < 2*n; j += j&-j) rightshift[j]--; } return res; }

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:23:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |         for(int j = 0; j < left[i].size(); j++)
      |                        ~~^~~~~~~~~~~~~~~~