Submission #935223

#	Time	Username	Problem	Language	Result	Execution time	Memory
935223		MinaRagy06	Fun Tour (APIO20_fun)	C++17	Compilation error	0 ms	0 KiB

fun

#include <bits/stdc++.h>
#ifdef MINA
#include "grader.cpp"
#endif
#include "fun.h"
using namespace std;
#define ll long long

vector<int> ans;
set<int> rem;
int n;
void solve(int i) {
	if (rem.find(i) == rem.end()) {
		return;
	}
	if ((i << 1) > n) {
		ans.push_back(i);
		rem.erase(ans.back());
		return;
	}
	rem.erase(i);
	vector<int> v[2];
	for (auto j : rem) {
		if (j == i) continue;
		int diff = __lg(j) - __lg(i << 1);
		v[(j >> diff) != (i << 1)].push_back(j);
	}
	int cur = 0;
	while (v[1].size()) {
		ans.push_back(v[cur].back());
		rem.erase(ans.back());
		v[cur].pop_back();
		cur ^= 1;
	}
	solve(i << 1);
	ans.push_back(i);
}
bool check(const std::vector<int>& fun_tour) {
  if (static_cast<int>(fun_tour.size()) != n) {
    return 0;
  }

  std::vector<bool> visited_attractions(N, false);
  for (int i = 0; i < n; ++i) {
    if (fun_tour[i] < 0 || fun_tour[i] >= n) {
    	return 0;
	}
    if (visited_attractions[fun_tour[i]]) {
    	return 0;
	}
    visited_attractions[fun_tour[i]] = true;
  }

  int last_travel_time = hoursRequired(fun_tour[0], fun_tour[1]);
  for (int i = 2; i < n; ++i) {
    int travel_time = hoursRequired(fun_tour[i - 1], fun_tour[i]);
    if (travel_time > last_travel_time) {
    	return 0;
	}
    last_travel_time = travel_time;
  }
  return 1;
}
vector<int> solve() {
	int dist[n][n]{};
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			dist[i][j] = hoursRequired(i, j);
		}
	}
	int u = 0;
	array<int, 2> mx = {-1, -1};
	for (int i = 0; i < n; i++) {
		mx = max(mx, {dist[u][i], i});
	}
	u = mx[1];
	vector<int> ans, v;
	for (int i = 0; i < n; i++) {
		if (i == u) continue;
		v.push_back(i);
	}
	ans.push_back(u);
	while (v.size()) {
		mx = {-1, -1};
		for (auto i : v) {
			mx = max(mx, {dist[u][i], i});
		}
		u = mx[1];
		ans.push_back(u);
		vector<int> newv;
		for (auto i : v) {
			if (i == u) continue;
			newv.push_back(i);
		}
		v = newv;
	}
	return ans;
}
vector<int> createFunTour(int _n, int q) {
	n = _n;
	N = n;
	if (n <= 500) {
		return solve();
	}
	for (int i = 1; i <= n; i++) {
		rem.insert(i);
	}
	solve(1);
	for (auto &i : ans) i--;
	if (!check(ans)) {
		return solve();
	}
	return ans;
}

Compilation message (stderr)

fun.cpp: In function 'bool check(const std::vector<int>&)':
fun.cpp:43:41: error: 'N' was not declared in this scope
   43 |   std::vector<bool> visited_attractions(N, false);
      |                                         ^
fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:101:2: error: 'N' was not declared in this scope
  101 |  N = n;
      |  ^