Submission #1088714

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088714		Joshua_Andersson	Jousting tournament (IOI12_tournament)	C++14	0 / 100	45 ms	11860 KiB

tournament

#if _LOCAL
#include "tournament.h"
#endif

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int inf = int(1e9);

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> p2;

#define rep(i, high) for (int i = 0; i < high; i++)
#define repp(i, low, high) for (int i = low; i < high; i++)
#define repe(i, container) for (auto& i : container)
#define sz(container) ((int)container.size())
#define all(x) begin(x),end(x)

inline void fast() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); }

#if _LOCAL
#define assert(x) if (!(x)) __debugbreak()
#endif

struct fenwick
{
	vi tree;
	fenwick(int n) : tree(n+1) {}

	void update(int i, int v)
	{
		for (i++; i < sz(tree); i += i & -i) tree[i] += v;
	}

	int query(int r)
	{
		int ret = 0;
		for (r++; r > 0; r -= r & -r) ret += tree[r];
		return ret;
	}

	int query(int l, int r) // [l,r]
	{
		if (l) l = query(l - 1);
		return query(r) - l;
	}
};

int GetBestPosition(int n, int c, int r, int *K, int *S, int *E)
{
	fenwick tree(n);
	rep(i, n) tree.update(i, 1);
	vi s(c);
	vi e(c);
	vi k(n-1);
	rep(i, n - 1) k[i] = K[i];
	rep(i, c) s[i] = S[i];
	rep(i, c) e[i] = E[i];

	vi par(n+c);
	vi leftmost_child(n+c,-1);
	vi nodes(n);
	rep(i, n) nodes[i] = i;

	rep(i, c)
	{
		int new_node = i + n;
		int l = e[i] - s[i] + 1;
		int u = -1;
		rep(j, l)
		{
			int lo = -1;
			int hi = n;
			while (lo+1<hi)
			{
				int mid = (lo + hi) / 2;
				if (tree.query(mid) >= s[i]+1)
				{
					hi = mid;
				}
				else lo = mid;
			}
			int v = nodes[hi];
			tree.update(hi, -1);
			if (leftmost_child[new_node]==-1)
			{
				leftmost_child[new_node] = v;
			}
			par[v] = new_node;
			u = hi;
		}
		assert(u != -1);
		nodes[u] = new_node;
		tree.update(u, 1);
	}

	vi color(n + c);
	vi must_shift(n + c);
	vector<p2> clean_depth(n + c, p2(0,inf));
	vector<p2> left_depth(n + c);
	vi good(n + c, 1);
	rep(i, n - 1) color[i + 1] = k[i] > r;
	rep(i, n) if (color[i]) must_shift[i] = 1;
	rep(i, n) left_depth[i].first = 1, left_depth[i].second=i, clean_depth[i].first=1, clean_depth[i].second=i;

	rep(i, sz(par)-1)
	{
		int p = par[i];
		if (clean_depth[i].first+1>clean_depth[p].first || (clean_depth[i].first + 1 == clean_depth[p].first)
			&& clean_depth[i].second<clean_depth[p].second)
		{
			clean_depth[p].first = clean_depth[i].first + 1;
			clean_depth[p].second = clean_depth[i].second;
		}
		if (!good[i]) good[par[i]]=0;

		if (i==leftmost_child[par[i]])
		{
			left_depth[p] = p2(left_depth[i].first+1, left_depth[i].second);
		}

		if (must_shift[i])
		{
			if (i != leftmost_child[par[i]])
			{
				good[par[i]] = 0;
			}
			must_shift[par[i]] = 1;
		}
	}

	p2 ans = p2(-inf, inf);
	rep(i, sz(par))
	{
		if (!good[i]) continue;
		if (must_shift[i])
		{
			if (left_depth[i].first>ans.first || (left_depth[i].first==ans.first && left_depth[i].second < ans.second))
			{
				ans = left_depth[i];
			}
		}
		else
		{
			if (clean_depth[i].first>ans.first || (clean_depth[i].first == ans.first && clean_depth[i].second < ans.second))
			{
				ans = clean_depth[i];
			}
		}
	}


	return ans.second;
}

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:112:4: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  111 |   if (clean_depth[i].first+1>clean_depth[p].first || (clean_depth[i].first + 1 == clean_depth[p].first)
      |                                                      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  112 |    && clean_depth[i].second<clean_depth[p].second)
      |    ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 17
• Subtask 2: 0 / 32
• Subtask 3: 0 / 51