Submission #350343

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

shoes

#include "shoes.h"

using namespace std;
#define MAXN 10001

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

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

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

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

public:
	Fenwick()
	{
		clear_array(a, N);
	}

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

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

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

long long count_adjacent()
{
	create_index();
	Fenwick f = Fenwick();
	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 - f.count(i, pos) - (shoes[i] < 0 ? 1 : 0);
			shoes[pos] = 0;
			f.put(pos);
		}
	}
	return ans;
}

void change(vector<int> v) {
	int cnt[N];
	clear_array(cnt, N);
	copy_arr(shoes, v, 2 * N);
	for (int i = 0; i < 2 * n; i++)
		if (v[i] > 0)
			cnt[v[i] - 1]++;

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

	vector<int> cntl = cnt, cntr = cnt;

	for (int i = 0; i < 2 * n; i++)
		if (v[i] > 0)
			v[i] = (--cntr[v[i] - 1]) + 1;
		else
			v[i] = -((--cntl[-v[i] - 1]) + 1);
}


long long count_swaps(vector<int> S)
{
	N = S.size / 2;
	change(S);
	return count_adjacent();
}

Compilation message (stderr)

shoes.cpp: In function 'void change(std::vector<int>)':
shoes.cpp:84:26: error: 'n' was not declared in this scope
   84 |  for (int i = 0; i < 2 * n; i++)
      |                          ^
shoes.cpp:88:22: error: 'n' was not declared in this scope
   88 |  for (int i = 1; i < n; i++)
      |                      ^
shoes.cpp:91:21: error: conversion from 'int [N]' to non-scalar type 'std::vector<int>' requested
   91 |  vector<int> cntl = cnt, cntr = cnt;
      |                     ^~~
shoes.cpp:91:33: error: conversion from 'int [N]' to non-scalar type 'std::vector<int>' requested
   91 |  vector<int> cntl = cnt, cntr = cnt;
      |                                 ^~~
shoes.cpp:93:26: error: 'n' was not declared in this scope
   93 |  for (int i = 0; i < 2 * n; i++)
      |                          ^
shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:103:8: error: invalid use of member function 'std::vector<_Tp, _Alloc>::size_type std::vector<_Tp, _Alloc>::size() const [with _Tp = int; _Alloc = std::allocator<int>; std::vector<_Tp, _Alloc>::size_type = long unsigned int]' (did you forget the '()' ?)
  103 |  N = S.size / 2;
      |      ~~^~~~
      |            ()