Submission #288982

#	Time	Username	Problem	Language	Result	Execution time	Memory
288982		Berted	Teams (IOI15_teams)	C++14	0 / 100	35 ms	8320 KiB

teams

#include "teams.h"
#include <iostream>
#include <utility>
#include <algorithm>
#include <vector>
#include <bitset>
#define pii pair<int, int>
#define fst first
#define snd second
 
const int SZ = (1 << 20) + 5, SZ2 = 500005;
 
using namespace std;
 
struct p_node
{
	int v = 0, l = -1, r = -1;
	p_node() {}
};
 
int n; pii a[105];
int pref[105], suf[105], t[105];
bool valid[105];
 
void init(int N, int A[], int B[]) 
{
	n = N;
	for (int i = 0; i < N; i++) {a[i] = {A[i], B[i]}; pref[B[i]]++; suf[A[i]]++;}
	for (int i = 1; i <= n + 1; i++) {pref[i] += pref[i - 1];}
	for (int i = n; i >= 0; i--) {suf[i] += suf[i + 1];}
}
 
int can(int M, int K[]) 
{
	//cout << "New " << M << "\n";
	sort(K, K + M);
	int ret = 1;
	for (int i = 0; i < M; i++)
	{
		valid[K[i]] = 1;
		if (i)
		{
			int add = 0;
			for (int j = 0; j < n; j++)
			{
				if (K[i - 1] < a[j].fst && a[j].snd < K[i]) {add++;}
			}
			for (int j = 1; j <= K[i - 1]; j++) {t[j] += add;}
		}
		for (int j = 1; j <= K[i]; j++) {t[j] += K[i];}
		for (int j = 1; j <= K[i]; j++)
		{
			//cout << i << " " << j << " " << pref[j - 1] << " " << suf[K[i] + 1] << " " << t[j] << "\n"; 
			if (valid[j] && pref[j - 1] + suf[K[i] + 1] + t[j] > n) {ret = 0;}
		}
	}
	for (int i = 0; i <= n + 2; i++) {t[i] = 0; valid[i] = 0;}
	return ret;
}

• Subtask 1: 0 / 21
• Subtask 2: 0 / 13
• Subtask 3: 0 / 43
• Subtask 4: 0 / 23