Submission #724237

#	Time	Username	Problem	Language	Result	Execution time	Memory
724237		badont	Arranging Shoes (IOI19_shoes)	C++17	Compilation error	0 ms	0 KiB

shoes

#include "shoes.h"
#include <cmath>
#include <cstdlib> 
#include <cassert>

template<typename T>
struct fen {
	vector<T> tr;
	ll mxn;

	fen(ll sz) {
		mxn = sz;
		tr.assign(sz + 5, 0);
	}

	void upd(ll g, T k) {
    g++;
		assert(g != 0);
		for (; g <= mxn; g += g&-g)
			tr[g] += k;
	}

	T ge(ll g) {
    g++;
		T res = 0;
		for (; g; g -= g&-g)
			res += tr[g];
		return res;
	}

	T rng(ll l, ll r) { if (l > r) return 0; return ge(r) - ge(l - 1); }
};

long long count_swaps(std::vector<int> s) {
	using ll = long long;
	using namespace std;
	ll n = (ll)s.size();
	n /= 2;
	vector<vector<ll>> pos(n, vector<ll>()), neg(n, vector<ll>());	

	for (int i = 0; i < 2 * n; i++) {
		ll x = abs(s[i]);
		if (s[i] < 0) {
			neg[x - 1].push_back(i);
		} else {
			pos[x - 1].push_back(i);
		}
	}

	ll op_1 = 0, op_2 = 0;
  vector<ll> match(n);
	for (int i = 0; i < n; i++) {
		assert(neg[i].size() == pos[i].size());
		for (int j = 0; j < (int)neg[i].size(); j++) {
			ll x = neg[i][j], y = pos[i][j];
      match[x] = y;
      match[y] = x;
			if (x > y) op_2++;
		}
	}

  fen<ll> tree(2 * n);
  for (int i = 0; i < 2 * n; i++)
    tree.upd(i, 1);

  for (int i = 0; i < 2 * n; i++) if (match[i] > i) {
    op_1 += tree.rng(i + 1, match[i] - 1);
 
   return op_1 + op_2;
}

Compilation message (stderr)

shoes.cpp:8:2: error: 'vector' does not name a type
    8 |  vector<T> tr;
      |  ^~~~~~
shoes.cpp:9:2: error: 'll' does not name a type
    9 |  ll mxn;
      |  ^~
shoes.cpp:11:8: error: expected ')' before 'sz'
   11 |  fen(ll sz) {
      |     ~  ^~~
      |        )
shoes.cpp:16:11: error: 'll' has not been declared
   16 |  void upd(ll g, T k) {
      |           ^~
shoes.cpp:23:7: error: 'll' has not been declared
   23 |  T ge(ll g) {
      |       ^~
shoes.cpp:31:8: error: 'll' has not been declared
   31 |  T rng(ll l, ll r) { if (l > r) return 0; return ge(r) - ge(l - 1); }
      |        ^~
shoes.cpp:31:14: error: 'll' has not been declared
   31 |  T rng(ll l, ll r) { if (l > r) return 0; return ge(r) - ge(l - 1); }
      |              ^~
shoes.cpp: In member function 'void fen<T>::upd(int, T)':
shoes.cpp:19:15: error: 'mxn' was not declared in this scope
   19 |   for (; g <= mxn; g += g&-g)
      |               ^~~
shoes.cpp:20:4: error: 'tr' was not declared in this scope
   20 |    tr[g] += k;
      |    ^~
shoes.cpp: In member function 'T fen<T>::ge(int)':
shoes.cpp:27:11: error: 'tr' was not declared in this scope
   27 |    res += tr[g];
      |           ^~
shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:62:21: error: no matching function for call to 'fen<long long int>::fen(ll)'
   62 |   fen<ll> tree(2 * n);
      |                     ^
shoes.cpp:7:8: note: candidate: 'constexpr fen<long long int>::fen()'
    7 | struct fen {
      |        ^~~
shoes.cpp:7:8: note:   candidate expects 0 arguments, 1 provided
shoes.cpp:7:8: note: candidate: 'constexpr fen<long long int>::fen(const fen<long long int>&)'
shoes.cpp:7:8: note:   no known conversion for argument 1 from 'll' {aka 'long long int'} to 'const fen<long long int>&'
shoes.cpp:7:8: note: candidate: 'constexpr fen<long long int>::fen(fen<long long int>&&)'
shoes.cpp:7:8: note:   no known conversion for argument 1 from 'll' {aka 'long long int'} to 'fen<long long int>&&'
shoes.cpp:71: note: '-Wmisleading-indentation' is disabled from this point onwards, since column-tracking was disabled due to the size of the code/headers
shoes.cpp:70:1: error: expected '}' at end of input
   70 | }
      | ^
shoes.cpp:34:43: note: to match this '{'
   34 | long long count_swaps(std::vector<int> s) {
      |                                           ^
shoes.cpp:39:40: warning: control reaches end of non-void function [-Wreturn-type]
   39 |  vector<vector<ll>> pos(n, vector<ll>()), neg(n, vector<ll>());
      |                                        ^