Submission #423624

#	Time	Username	Problem	Language	Result	Execution time	Memory
423624		Mazaalai	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	1 ms	204 KiB

shoes

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

long long count_swaps(vector<int> s) {
	ll ans = 0, n = s.size();
	map <int, vector <int> > l, r;
	for (int i = 0; i < n; i++) {
		if (s[i] < 0) 
			l[-s[i]].push_back(i);
		else
			r[s[i]].push_back(i);
	}
	vector <pair <int, int> > lines;
	vector <int> lineCnt(n+5, 0);
	for (auto el : l) {
		int val = el.first;
		vector <int> a = el.second, b = r[val];
		for (int i = 0; i < a.size(); i++) {
			int x = a[i], y = b[i];
			if (x < y && x + 1 <= y) {
				ans += y - (x+1);
				lines.push_back({x+1, y});
				// cout << x+1 << ' ' << y <<": ";
				lineCnt[x+1]++;
				// cout << "line1: " << x+1;
				lineCnt[y+1]--;
				// cout << ", " << y << '\n';
			}
			if (x > y && y <= x-1) {
				swap(x, y);
				ans += y - x;
				lines.push_back({x, y});
				// cout << x << ' ' << y <<": ";
				lineCnt[x]++;
				// cout << "line2: " << x;
				lineCnt[y+1]--;
				// cout << ", " << y << '\n';
			}
		}
	}
	// cout << ans << '\n';
	for (int i = 1; i < n+5; i++) lineCnt[i] += lineCnt[i-1];
	// for (int i = 0; i < n; i++) cout << lineCnt[i] << ' ';
	// cout << '\n';
	for (auto [a, b] : lines) {
		// cout << a << ' ' << b << '\n';
		if (lineCnt[a] != lineCnt[b]) {
			// cout << a << ' ' << b << ' ' << lineCnt[a] << ' ' << lineCnt[b] << '\n';
			ans -= abs(lineCnt[b] - lineCnt[a]);
		}
	}

	// sort(lines.begin(), lines.end());
	// for 
	return ans;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:20:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |   for (int i = 0; i < a.size(); i++) {
      |                   ~~^~~~~~~~~~
shoes.cpp:47:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   47 |  for (auto [a, b] : lines) {
      |            ^

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