Submission #500982

#	Time	Username	Problem	Language	Result	Execution time	Memory
500982		aryan12	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	99 ms	18744 KiB

shoes

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

const long long N = 2e5 + 5;
long long BIT[N];

bool cmp(pair<long long, long long> a, pair<long long, long long> b) {
	return (a.second - a.first) < (b.second - b.first);
}

void Update(long long idx, long long val) {
	for(long long i = idx; i < N; i += (i & (-i))) {
		BIT[i] += val;
	}
}

long long Query(long long x) {
	long long ans = 0;
	for(long long i = x; i > 0; i -= (i & (-i))) {
		ans += BIT[i];
	}
	return ans;
}

long long count_swaps(vector<int> input) {
	long long n = input.size();
	vector<pair<long long, long long> > pair_of_shoes;
	vector<long long> pos(n + 1), idx[n + 1];
	for(long long i = 0; i <= n; i++) {
		pos[i] = 0;
	}
	for(long long i = 0; i < n; i++) {
		if(input[i] > 0) {
			input[i] += n / 2;
		}
		else {
			input[i] = abs(input[i]);
		}
		//cout << "input[i] = " << input[i] << "\n";
		idx[input[i]].push_back(i);
		if(input[i] > n / 2) {
			if(pos[input[i] - n / 2] != idx[input[i] - n / 2].size()) {
				long long pos1 = idx[input[i] - n / 2][pos[input[i] - n / 2]], pos2 = idx[input[i]][pos[input[i]]];
				pair_of_shoes.push_back(make_pair(idx[input[i] - n / 2][pos[input[i] - n / 2]], idx[input[i]][pos[input[i]]]));
				pos[input[i] - n / 2]++;
				pos[input[i]]++;
				//cout << "pos1 = " << pos1 << ", pos2 = " << pos2 << " hi\n";
			}
		}
		if(input[i] <= n / 2) {
			if(pos[input[i] + n / 2] != idx[input[i] + n / 2].size()) {
				long long pos1 = idx[input[i] + n / 2][pos[input[i] + n / 2]], pos2 = idx[input[i]][pos[input[i]]];
				pair_of_shoes.push_back(make_pair(idx[input[i] + n / 2][pos[input[i] + n / 2]], idx[input[i]][pos[input[i]]]));
				pos[input[i] + n / 2]++;
				pos[input[i]]++;
				//cout << "pos1 = " << pos1 << ", pos2 = " << pos2 << " omg\n";
			}
		}
	}
	long long ans = 0, res = 0;
	sort(pair_of_shoes.begin(), pair_of_shoes.end(), cmp);
	for(long long i = 0; i < pair_of_shoes.size(); i++) {
		ans += pair_of_shoes[i].second - pair_of_shoes[i].first - 1;
		if(input[pair_of_shoes[i].first] > input[pair_of_shoes[i].second]) {
			ans++;
		}
		pair_of_shoes[i].first++;
		pair_of_shoes[i].second++;
		//cout << pair_of_shoes[i].first << " " << pair_of_shoes[i].second << "\n";
		if(pair_of_shoes[i].first != pair_of_shoes[i].second - 1) {
			Update(pair_of_shoes[i].first + 1, 1);
			Update(pair_of_shoes[i].second, -1);
			long long temp = Query(pair_of_shoes[i].first); //whoever started before pair_of_shoes[i].first
			long long ok = Query(pair_of_shoes[i].second); //whoever started in the middle (also contains the ones which started before pair_of_shoes[i].first)
			res += ok + temp;
			//cout << "ok = " << ok << ", temp = " << temp << "\n";
		}
	}
	/*long long res = 0;
	for(long long i = 0; i < pair_of_shoes.size(); i++) {
		res += Query(1LL, pair_of_shoes[i].first) + Query(pair_of_shoes[i].first, pair_of_shoes[i].second) - Query;
	}
	res /= 2;*/
	return ans - res;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:43:29: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |    if(pos[input[i] - n / 2] != idx[input[i] - n / 2].size()) {
shoes.cpp:44:15: warning: unused variable 'pos1' [-Wunused-variable]
   44 |     long long pos1 = idx[input[i] - n / 2][pos[input[i] - n / 2]], pos2 = idx[input[i]][pos[input[i]]];
      |               ^~~~
shoes.cpp:44:68: warning: unused variable 'pos2' [-Wunused-variable]
   44 |     long long pos1 = idx[input[i] - n / 2][pos[input[i] - n / 2]], pos2 = idx[input[i]][pos[input[i]]];
      |                                                                    ^~~~
shoes.cpp:52:29: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |    if(pos[input[i] + n / 2] != idx[input[i] + n / 2].size()) {
shoes.cpp:53:15: warning: unused variable 'pos1' [-Wunused-variable]
   53 |     long long pos1 = idx[input[i] + n / 2][pos[input[i] + n / 2]], pos2 = idx[input[i]][pos[input[i]]];
      |               ^~~~
shoes.cpp:53:68: warning: unused variable 'pos2' [-Wunused-variable]
   53 |     long long pos1 = idx[input[i] + n / 2][pos[input[i] + n / 2]], pos2 = idx[input[i]][pos[input[i]]];
      |                                                                    ^~~~
shoes.cpp:63:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |  for(long long i = 0; i < pair_of_shoes.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