Submission #285138

#	Time	Username	Problem	Language	Result	Execution time	Memory
285138		cookiedoth	Arranging Shoes (IOI19_shoes)	C++14	50 / 100	1087 ms	26616 KiB

shoes

/*

Code for problem A by cookiedoth
Generated 28 Aug 2020 at 01.11 PM


______▄███████▄_______
______█▄█████▄█_______
______█▼▼▼▼▼█_______
_____██________ ██______
______█▲▲▲▲▲█_______
______█████████_______
_______██____ ██________

=_=
¯\_(ツ)_/¯
o_O

*/

#include "shoes.h"
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <map>
#include <bitset>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <ctime>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <complex>
#include <cassert>
#include <random>
#include <cstring>
#include <numeric>
#include <random>
#define ll long long
#define ld long double
#define null NULL
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define debug(a) cerr << #a << " = " << a << endl
#define forn(i, n) for (int i = 0; i < n; ++i)
#define length(a) (int)a.size()

using namespace std;

template<class T> int chkmax(T &a, T b) {
	if (b > a) {
		a = b;
		return 1;
	}
	return 0;
}

template<class T> int chkmin(T &a, T b) {
	if (b < a) {
		a = b;
		return 1;
	}
	return 0;
}

template<class iterator> void output(iterator begin, iterator end, ostream& out = cerr) {
	while (begin != end) {
		out << (*begin) << " ";
		begin++;
	}
	out << endl;
}

template<class T> void output(T x, ostream& out = cerr) {
	output(x.begin(), x.end(), out);
}

void fast_io() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}

map<int, vector<int> > L, R;
vector<int> flip, used;
int n;
ll ans;

void add_pair(int i, int j) {
	if (i > j) {
		ans++;
	}
	flip[i] = j;
	flip[j] = i;
}

ll count_swaps(vector<int> s) {
	n = s.size();
	for (int i = 0; i < n; ++i) {
		if (s[i] < 0) {
			L[s[i]].push_back(i);
		} else {
			R[-s[i]].push_back(i);
		}
	}
	flip.resize(n);
	for (auto pp : L) {
		vector<int> vL = pp.second, vR = R[pp.first];
		for (int i = 0; i < vL.size(); ++i) {
			add_pair(vL[i], vR[i]);
		}
	}
	used.resize(n);
	for (int i = 0; i < n; ++i) {
		if (used[i] == 0) {
			for (int j = i + 1; j < flip[i]; ++j) {
				ans += (used[j] == 0);
			}
			used[i] = 1;
			used[flip[i]] = 1;
		}
	}
	return ans;
}

Compilation message (stderr)

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

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