Submission #1246523

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246523		countless	Teams (IOI15_teams)	C++20	34 / 100	4091 ms	35512 KiB

teams

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

typedef long long ll;
typedef long double ld;

#define sp <<" "<<
#define endl "\n"

int n;
vector<int> a, b, o, p; // you're a bop

void init(int N, int A[], int B[]) {
	n = N;
	a.resize(n), b.resize(n), o.resize(n), p.resize(n);
	for (int i = 0; i < n; i++) {
		a[i] = A[i], b[i] = B[i];
	}

	iota(o.begin(), o.end(), 0);
	sort(o.begin(), o.end(), [&](int i, int j) {
		return a[i] < a[j];
	});

	iota(p.begin(), p.end(), 0);
	sort(p.begin(), p.end(), [&](int i, int j) {
		return b[i] < b[j];
	});
}

int can(int M, int K[]) {
	int m = M;
	vector<int> k(m);
	ll sum = 0;
	for (int i = 0; i < m; i++) {
		k[i] = K[i];
		sum += k[i];
	}
	
	if (sum > n) return 0;
	sort(k.begin(), k.end());
	
	multiset<int> pq;
	int addl = 0, addr = 0;
	int reml = 0, remr = 0;

	for (int i = 0; i < M; i++) {
		// cerr << "let's process" sp k[i] << endl;
		while (addr < n and a[o[addr]] <= k[i]) addr++;
		for (int j = addl; j < addr; j++) {
			// cerr << "adding:" sp a[o[j]] sp b[o[j]] << endl;
			pq.insert(b[o[j]]);
		}
		addl = addr;

		while (remr < n and b[p[remr]] < k[i]) remr++;
		for (int j = reml; j < remr; j++) {
			// cerr << "removing:" sp a[p[j]] sp b[p[j]] << endl;
			auto it = pq.find(b[p[j]]);
			if (it != pq.end()) pq.erase(it);
		}
		reml = remr;

		// cerr << "in set" sp pq.size() << endl;
		for (int j = 0; j < k[i]; j++) {
			if (pq.empty()) return 0;
			pq.erase(pq.begin());
		}
	}

	return 1;
}

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