Submission #30722

#	Time	Username	Problem	Language	Result	Execution time	Memory
30722		rondojim	Teams (IOI15_teams)	C++14	34 / 100	4000 ms	24080 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX = (1e5)+1;
 
int n, a[MAX], b[MAX];
set<pair<int,int> > f[MAX];
 
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];
		f[A[i]].emplace(0, i);
		f[B[i]].emplace(1, i);
	}
}
 
int can(int M, int K[]) {
	sort(K, K+M);
	set<pair<int,int> > st;
	vector<pair<int,int> > add_back;
	bool valid = true;
	for(int j = 1, i = 0; j <= n; j++) {
		for(auto p: f[j]) if(!p.first) st.emplace(b[p.second], p.second);
		while(i < M && j == K[i]) {
			valid &= st.size() >= K[i];
			if(!valid) {
				for(auto p: add_back) f[p.first].emplace(1, p.second);
				return 0;
			}
			for(int cnt = 0; cnt < K[i]; cnt++) {
				add_back.push_back(*st.begin());
				f[st.begin()->first].erase(make_pair(1, st.begin()->second));
				st.erase(st.begin());
			}
			i++;
		}
		for(auto p: f[j]) if(p.first) st.erase(make_pair(b[p.second], p.second));
	}
	for(auto p: add_back) f[p.first].emplace(1, p.second);
	return 1;
}

Compilation message (stderr)

teams.cpp: In function 'int can(int, int*)':
teams.cpp:27:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    valid &= st.size() >= K[i];
                       ^

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