Submission #1051622

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051622		Tob	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	33 ms	15644 KiB

shoes

#include <bits/stdc++.h>

#include "shoes.h"

#define F first
#define S second

using namespace std;

typedef long long ll;

const int N = 2e5 + 7;

int fen[N];
vector <int> v[N];

void add(int x, int val) {for (x++; x < N; x += x & -x) fen[x] += val;}
int get(int x) {int out = 0; for (x++; x; x -= x & -x) out += fen[x]; return out;}

ll count_swaps(vector <int> a) {
	int n = a.size();
	
	vector <int> pa(n, -1);
	for (int i = 0; i < n; i++) v[a[i]+n/2].push_back(i);
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j < v[i].size(); j++) pa[min(v[i][j], v[n-i][j])] = max(v[i][j], v[n-i][j]);
	}
	
	ll res = 0;
	for (int i = 0; i < n; i++) {
		if (pa[i] == -1) continue;
		res += pa[i]-i-(a[i] < 0) - get(pa[i])+get(i);
		add(pa[i], 1);
	}
	
	return res;
}

Compilation message (stderr)

shoes.cpp: In function 'll count_swaps(std::vector<int>)':
shoes.cpp:26:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |   for (int j = 0; j < v[i].size(); j++) pa[min(v[i][j], v[n-i][j])] = max(v[i][j], v[n-i][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