Submission #1125819

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125819		AngusRitossa	Mountains (IOI17_mountains)	C++20	40 / 100	3 ms	840 KiB

mountains

#include "mountains.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
#ifdef LOCAL
#define err cout
#else
#define err if (0) cout
#endif

vector<vector<int>> make_graph (vector<int> y){
	int n = y.size();
	vector<vector<int>> ret(n);
	for (int i = 0; i < n; i++){
		vector<int> vt(n-i-1);
		iota(vt.begin(), vt.end(), i+1);
		sort(vt.begin(), vt.end(), [&](int a, int b){
			if ((y[a]-y[i])*(b-i) == (y[b]-y[i])*(a-i))
				return a > b;
			return (y[a]-y[i])*(b-i) > (y[b]-y[i])*(a-i);
		});
		int mn = INT_MAX;
		for (int j : vt){
			if (mn > j){
				ret[i].push_back(j);
				ret[j].push_back(i);
			}
			mn = min(mn, j);
		}
	}
	return ret;
}

signed maximum_deevs(std::vector<signed> y){
	vector<int> z;
	for (int i : y)
		z.push_back(i);
	auto adj = make_graph(z);
	int n = y.size();
	vector<int> cnt(n);
	vector<bool> been(n, 0), bad(n, 0);
	for (int i = 0; i < n; i++)
		cnt[i] = adj[i].size();
	for (int k = n; k--;){
		pair<int, int> best = {INT_MAX, -1};
		for (int i = 0; i < n; i++)
			if (!been[i] && !bad[i])
				best = min(best, {cnt[i], i});
		if (!~best.s)
			break;
		been[best.s] = true;
		for (int i : adj[best.s]){
			if (bad[i])
				continue;
			if (been[i])
				continue;
			bad[i] = true;
			for (int j : adj[i])
				cnt[j]--;
		}
	}
	return count(bad.begin(), bad.end(), 0);
}

#undef int
#undef f
#undef s
#undef err

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30