Submission #242869

#	Time	Username	Problem	Language	Result	Execution time	Memory
242869		godwind	Teams (IOI15_teams)	C++14	34 / 100	4097 ms	17912 KiB

teams

#include "teams.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <set>
#include <map>
#include <queue>
#include <cstring>
#include <cmath>
#include <bitset>
#include <iomanip>
#include <functional>

using namespace std;

const int N = 100 * 1000 + 228;

int n;
int a[N], b[N];

struct seg
{
	int l, r, id;
	seg() {}
	seg(int _l, int _r, int _id) {
		l = _l;
		r = _r;
		id = _id;
	}
};
bool operator<(seg fir, seg sec) {
	return fir.r < sec.r || (fir.r == sec.r && fir.id < sec.id);
}

vector< seg > open[N], close[N];

void init(int N, int A[], int B[]) {
	n = N;
	for (int i = 0; i < n; ++i) {
		a[i] = A[i];
		b[i] = B[i];
		open[a[i]].emplace_back(seg(a[i], b[i], i));
		close[b[i]].emplace_back(seg(a[i], b[i], i));
	}
}

int cnt[N];

int can(int M, int K[]) {
	for (int i = 0; i <= n; ++i) {
		cnt[i] = 0;
	}
	int sum_all = 0;
	for (int i = 0; i < M; ++i) {
		sum_all += K[i];
		if (sum_all > n) {
			return 0;
		}
		++cnt[K[i]];
	}
	sort(K, K + M);

	set< seg > s;

	for (int x = 1; x <= n; ++x) {
		for (seg sg : close[x - 1]) {
			if (s.count(sg)) {
				s.erase(sg);
			}
		}
		for (seg sg : open[x]) {
			s.insert(sg);
		}

		for (int it = 0; it < x * cnt[x]; ++it) {
			if (s.empty()) {
				return 0;
			}
			s.erase(s.begin());
		}

	}

	return 1;
}

Compilation message (stderr)

teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:38:34: warning: declaration of 'N' shadows a global declaration [-Wshadow]
 void init(int N, int A[], int B[]) {
                                  ^
teams.cpp:17:11: note: shadowed declaration is here
 const int N = 100 * 1000 + 228;
           ^

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