Submission #350514

#	Time	Username	Problem	Language	Result	Execution time	Memory
350514		phenius	Arranging Shoes (IOI19_shoes)	C++14	Compilation error	0 ms	0 KiB

shoes

#include <iostream>
#include <string>

using namespace std;
#define MAXN 100000

int a[2 * MAXN];
int shoes[2 * MAXN];
int index[2 * MAXN + 1];
int cnt[MAXN], cntl[MAXN];
int N;

void clear_array(int *ar, int n) {
	for (int i = 0; i < n; i++)
		ar[i] = 0;
}

void copy_arr(int *a1, int *a2, int n) {
	for (int i = 0; i < n; i++)
		a1[i] = a2[i];
}

void copy_arr(int *a1, vector <int> a2, int n) {
	for (int i = 0; i < n; i++)
		a1[i] = a2[i];
}

class BIT
{
	int count(int right)
	{
		int cnt = 0;
		for (; right >= 0; right = (right & (right + 1)) - 1)
		{
			cnt += a[right];
		}
		return cnt;
	}

public:
	BIT()
	{
		clear_array(a, 2 * N);
	}

	int count(int left, int right)
	{
		return count(right) - count(left - 1);
	}

	void insert(int index)
	{
		for (; index < 2 * N; index = index | (index + 1))
		{
			a[index]++;
		}
	}
};

void create_index()
{
	clear_array(index, 2 * N + 1);
	for (int i = 0; i < 2 * N; i++)
	{
		index[shoes[i] + N] = i;
	}
}

void convert() {
	clear_array(cnt, N);

	for (int i = 0; i < 2 * N; i++)
		if (shoes[i] > 0)
			cnt[shoes[i] - 1]++;

	for (int i = 1; i < N; i++)
		cnt[i] += cnt[i - 1];

	copy_arr(cntl, cnt, N);

	for (int i = 0; i < 2 * N; i++)
		if (shoes[i] > 0)
			shoes[i] = (--cntl[shoes[i] - 1]) + 1;
		else
			shoes[i] = -((--cnt[-shoes[i] - 1]) + 1);
}

long long count_swaps(vector<int> S)
{
	N = S.size() / 2;
	copy_arr(shoes, S, 2 * N);
	
	convert();
	create_index();
	BIT tree = BIT();

	long long ans = 0;

	for (int i = 0; i < 2 * N; i++)
	{
		if (shoes[i] != 0)
		{
			int pos = index[-shoes[i] + N];
			ans += pos - i - tree.count(i, pos) - (shoes[i] < 0 ? 1 : 0);
			shoes[pos] = 0;
			tree.insert(pos);
		}
	}
	return ans;
}

Compilation message (stderr)

shoes.cpp:23:24: error: 'vector' has not been declared
   23 | void copy_arr(int *a1, vector <int> a2, int n) {
      |                        ^~~~~~
shoes.cpp:23:31: error: expected ',' or '...' before '<' token
   23 | void copy_arr(int *a1, vector <int> a2, int n) {
      |                               ^
shoes.cpp: In function 'void copy_arr(int*, int)':
shoes.cpp:24:22: error: 'n' was not declared in this scope
   24 |  for (int i = 0; i < n; i++)
      |                      ^
shoes.cpp:25:11: error: 'a2' was not declared in this scope; did you mean 'a1'?
   25 |   a1[i] = a2[i];
      |           ^~
      |           a1
shoes.cpp: At global scope:
shoes.cpp:88:23: error: 'vector' was not declared in this scope
   88 | long long count_swaps(vector<int> S)
      |                       ^~~~~~
shoes.cpp:2:1: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
    1 | #include <iostream>
  +++ |+#include <vector>
    2 | #include <string>
shoes.cpp:88:30: error: expected primary-expression before 'int'
   88 | long long count_swaps(vector<int> S)
      |                              ^~~