Submission #287296

#	Time	Username	Problem	Language	Result	Execution time	Memory
287296		amoo_safar	Teams (IOI15_teams)	C++17	34 / 100	4067 ms	14840 KiB

teams

#include "teams.h"

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

const int N = 1e5 + 10;

int n, A[N], B[N];
vector<int> st[N];
void init(int _n, int _A[], int _B[]) {
	n = _n;
	for(int i = 0; i < n; i++) A[i] = _A[i];
	for(int i = 0; i < n; i++) B[i] = _B[i] + 1;
	for(int i = 0; i < n; i++) st[A[i]].pb(B[i]);
}

priority_queue< int, vector<int>, greater<int> > pq;
int K[N];
int can(int m, int _K[]){
	for(int i = 0; i < m; i++) K[i] = _K[i];
	while(!pq.empty()) pq.pop();
	
	int sm = 0;
	for(int i = 0; i < m; i++){
		sm += K[i];
		if(sm > n) return 0;
	}
	sort(K, K + m);
	int rq, fr, p = -1;
	for(int i = 0; i < m; i++){
		while(p < K[i]){
			p ++;
			for(auto &x : st[p])
				pq.push(x);
		}
		rq = K[i];
		while(!pq.empty() && rq){
			fr = pq.top();
			pq.pop();
			if(fr > K[i]) rq --;
		}
		if(rq) return 0;
	}
	return 1;
}

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