Submission #724306

#	Time	Username	Problem	Language	Result	Execution time	Memory
724306		QwertyPi	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	264 ms	33180 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 11;
struct BIT{
	int bit[N * 2];
	void add(int p, int v){
		p++;
		for(int i = p; i < N * 2; i += i & -i){
			bit[i] += v;
		}
	}
	int qry(int p){
		p++;
		int ret = 0;
		for(int i = p; i; i -= i & -i){
			ret += bit[i];
		}
		return ret;
	}
} bit;

long long count_swaps(vector<int> s) {
	map<int, vector<int>> M;
	for(int i = 0; i < s.size(); i++){
		M[s[i]].push_back(i);
	}
	long long ans = 0; vector<pair<int, int>> vp;
	for(int i = 1; i <= s.size(); i++){
		int k = M[i].size();
		for(int j = 0; j < k; j++){
			int x = M[i][j], y = M[-i][j];
			if(x < y) ans++; if(x > y) swap(x, y);
			vp.push_back({x, y});
		}
	}
	sort(vp.begin(), vp.end());
	for(int i = 0; i < s.size(); i++) bit.add(i, 1);
	for(auto i : vp){
		bit.add(i.first, -1);
		bit.add(i.second, -1);
		ans += bit.qry(i.second);
	}
	return ans;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:25:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |  for(int i = 0; i < s.size(); i++){
      |                 ~~^~~~~~~~~~
shoes.cpp:29:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |  for(int i = 1; i <= s.size(); i++){
      |                 ~~^~~~~~~~~~~
shoes.cpp:33:4: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   33 |    if(x < y) ans++; if(x > y) swap(x, y);
      |    ^~
shoes.cpp:33:21: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   33 |    if(x < y) ans++; if(x > y) swap(x, y);
      |                     ^~
shoes.cpp:38:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |  for(int i = 0; i < s.size(); i++) bit.add(i, 1);
      |                 ~~^~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15