Submission #158354

#	Time	Username	Problem	Language	Result	Execution time	Memory
158354		johutha	Teams (IOI15_teams)	C++14	34 / 100	4034 ms	44864 KiB

teams

#include "teams.h"
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>


using namespace std;

struct event
{
	int tm;
	int pr = -1;
	int nr = -1;
};

bool evsort(event e1, event e2)
{
	if (e1.tm != e2.tm) return e1.tm < e2.tm;
	return e1.pr < e2.pr;
}

vector<event> evs;
vector<int> st;
vector<int> en;

void init(int N, int A[], int B[]) 
{
	for (int i = 0; i < N; i++)
	{
		st.push_back(A[i]);
		en.push_back(B[i]);
		event nw;
		nw.tm = A[i];
		nw.nr = i;
		nw.pr = -1;
		evs.push_back(nw);
		event ene;
		ene.tm = B[i];
		ene.nr = i;
		ene.pr = 1;
		evs.push_back(ene);
	}
}

int can(int M, int K[])
{
	vector<event> evcopy = evs;
	for (int i = 0; i < M; i++)
	{
		event mev;
		mev.tm = K[i];
		mev.nr = -1;
		mev.pr = 0;
		evcopy.push_back(mev);
	}
	sort(evcopy.begin(), evcopy.end(), evsort);

	multiset<int> active;
	for (auto e : evcopy)
	{
		if (e.pr == 0)
		{
			if (active.size() < e.tm)
			{
				return 0;
			}
			auto it = active.begin();
			for (int i = 0; i < e.tm; i++)
			{
				it = active.erase(it);
			}
		}
		else if (e.pr == -1)
		{
			active.insert(en[e.nr]);
		}
		else
		{
			if (active.find(e.tm) != active.end()) active.erase(active.find(e.tm));
		}
	}
	return 1;
}

Compilation message (stderr)

teams.cpp: In function 'int can(int, int*)':
teams.cpp:64:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (active.size() < e.tm)
        ~~~~~~~~~~~~~~^~~~~~

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