Submission #1065125

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065125		pawned	Teams (IOI15_teams)	C++17	34 / 100	4065 ms	42428 KiB

teams

#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")

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

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;

#include "teams.h"

const int MAX = 1e5 + 5;	// change to 1e5 + 5 later

int N;
vector<ii> allp;

void init(int N_g, int A_g[], int B_g[]) {
	N = N_g;
	for (int i = 0; i < N; i++) {
		allp.pb({A_g[i], B_g[i]});
	}
}

int can(int M, int K_g[]) {
	vi teams;
	for (int i = 0; i < M; i++) {
		teams.pb(K_g[i]);
	}
	sort(teams.begin(), teams.end());
	multiset<int> tr1[MAX];	// all end with start equal to i
	multiset<int> tr2[MAX];	// all start with end equal to i
	for (ii p : allp) {
		tr1[p.fi].insert(p.se);
		tr2[p.se].insert(p.fi);
	}
	multiset<ii> have;	// all eligible {end, start}
	// at each time, get best
	int curr = 0;	// minimum start
	for (int i = 0; i < M; i++) {
//		cout<<"at "<<i<<endl;
		for (int j = curr + 1; j <= teams[i]; j++) {	// add starting w/ j
			for (int x : tr1[j]) {
//				cout<<"inserting "<<x<<" "<<j<<endl;
				have.insert({x, j});
			}
		}
		for (int j = curr; j < teams[i]; j++) {	// remove ending w/ j
			for (int x : tr2[j]) {
				have.erase(have.find({j, x}));
			}
			tr2[j].clear();
		}
		curr = teams[i];
		for (int j = 0; j < teams[i]; j++) {	// find team[i] of val team[i]
//			cout<<"j: "<<j<<endl;
			if (have.size() == 0)	// run out
				return 0;
			ii minv = *(have.begin());	// lowest end, greedy
//			cout<<"minv: "<<minv.fi<<", "<<minv.se<<endl;
			have.erase(have.find(minv));
			tr1[minv.se].erase(tr1[minv.se].find(minv.fi));
			tr2[minv.fi].erase(tr2[minv.fi].find(minv.se));
		}
	}
	return 1;
}

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