Submission #143939

#	Time	Username	Problem	Language	Result	Execution time	Memory
143939		tincamatei	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	111 ms	14844 KiB

shoes

#include "shoes.h"
#include <vector>
#include <cstdlib>
#include <cstdio>

using namespace std;

vector<int> aib;

static inline int lsb(int x) {
	return x & (-x);
}

void update(int poz, int val) {
	while(poz <= aib.size()) {
		aib[poz] += val;
		poz += lsb(poz);
	}
}

int query(int poz) {
	int rez = 0;
	while(poz > 0) {
		rez += aib[poz];
		poz -= lsb(poz);
	}
	return rez;
}

long long sweep(const vector<int> &x) {
	int N = x.size() / 2;
	long long rez = 0LL;
	vector<int> last(1 + N, -1);
	for(int i = 0; i < 2 * N; ++i) {
		if(last[abs(x[i])] == -1)
			last[abs(x[i])] = i + 1;
		else {
			rez = rez + query(i) - query(last[abs(x[i])]);
			update(i + 1, 1);
			update(last[abs(x[i])], 1);

			if(x[i] < 0)
				++rez;
		}
	}

	return rez;
}

long long count_swaps(std::vector<int> s) {
	int N = s.size() / 2;
	vector<vector<int> > pozLeft(N), pozRight(N);
	vector<int> norm(2 * N);
	for(int i = 0; i < 2 * N; ++i)
		if(s[i] < 0)
			pozLeft[-s[i] - 1].push_back(i);
		else
			pozRight[s[i] - 1].push_back(i);
	
	int id = 0;
	for(int i = 0; i < N; ++i) {
		for(int j = 0; j < pozLeft[i].size(); ++j) {
			++id;
			norm[pozLeft[i][j]] = -id;
			norm[pozRight[i][j]] = id;
		}
	}

	aib.clear();
	aib.resize(1 + 2 * N, 0);

	return sweep(norm);
}

Compilation message (stderr)

shoes.cpp: In function 'void update(int, int)':
shoes.cpp:15:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(poz <= aib.size()) {
        ~~~~^~~~~~~~~~~~~
shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:62:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < pozLeft[i].size(); ++j) {
                  ~~^~~~~~~~~~~~~~~~~~~

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