Submission #568528

#	Time	Username	Problem	Language	Result	Execution time	Memory
568528		CSQ31	Teams (IOI15_teams)	C++17	0 / 100	100 ms	16852 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define fi first
#define se second
int n;
vector<pii>r;
void init(int N, int A[], int B[]) {
	n = N;
	for(int i=0;i<n;i++)r.push_back({A[i],B[i]});
	sort(r.begin(),r.end());
}

int can(int m, int K[]) {
	int sum = 0;
	map<int,int>cnt;
	for(int i=0;i<m;i++){
		sum+=K[i];
		cnt[K[i]]++;
		if(sum>n)return 0;
	}
	vector<pii>a;
	for(auto x:cnt)a.push_back(x);
	int s = a.size();
	vector<int>need(s,0);
	assert(s<=450);
	for(int i=0;i<s;i++)need[i] = a[i].fi * a[i].se;
	int ptr = -1;
	multiset<int>w;
	for(int i=0;i<s;i++){
		int last = ptr;
		while(ptr+1<n && r[ptr+1].fi<=a[i].fi)ptr++;
		//cout<<last<<" "<<ptr<<'\n';
		for(int j=last+1;j<=ptr;j++)w.insert(r[j].se);
		while(!w.empty() && *w.begin() < a[i].fi)w.erase(w.begin());
		while(!w.empty() && need[i]){
			w.erase(w.begin());
			need[i]--;
		}
		
	}
	for(int x:need)cout<<x<<" ";
	for(int x:need){
		if(x)return 0;
	}
	return 1;
}

Compilation message (stderr)

teams.cpp: In function 'int can(int, int*)':
teams.cpp:25:16: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   25 |  int s = a.size();
      |          ~~~~~~^~

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