Submission #1188735

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188735		DobromirAngelov	Teams (IOI15_teams)	C++20	34 / 100	4096 ms	9524 KiB

teams

#include "teams.h"
#include<bits/stdc++.h>
#define fi first
#define se second

using namespace std;

const int MAXN=5e5+5;
const int MAXM=5e5+5;

int n;
pair<int,int> a[MAXN];

void init(int N, int A[], int B[]) 
{
	n=N;
	for(int i=1;i<=n;i++)
	{
		a[i]={A[i-1], B[i-1]};
	}

	sort(a+1,a+n+1,[](pair<int,int> x,pair<int,int> y){
		return x.se<y.se;
	});
}

int m;
int qr[MAXM];
vector<pair<int,int> > qs;
bool used[MAXN];
int can(int M, int K[]) 
{
	m=M;
	for(int i=1;i<=M;i++) qr[i]=K[i-1];
	qs.clear();

	long long sum=0;
	for(int i=1;i<=m;i++) sum+=qr[i];
	if(sum>n) return 0;

	sort(qr+1,qr+m+1);
	int cnt=1;
	for(int i=1;i<=m;i++)
	{
		if(qr[i]==qr[i-1]) cnt++;
		else
		{
			if(i>1) qs.push_back({qr[i-1],cnt});
			cnt=1;
		}
	}
	qs.push_back({qr[m],cnt});

	for(int i=1;i<=n;i++) used[i]=0;
	for(auto [x,cnt]: qs)
	{
		int tmp=x*cnt;
		for(int i=1;i<=n;i++)
		{
			if(tmp==0) break;
			if(a[i].se<x) continue;
			if(a[i].fi<=x && !used[i])
			{
				tmp--;
				used[i]=1;
			}
		}
		if(tmp>0) return 0;
	}
	return 1;
}

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