Submission #1061774

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061774		anango	Teams (IOI15_teams)	C++17	34 / 100	4067 ms	57828 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;

int debug = 0;
int n;
vector<pair<int,int>> students;
vector<int> ar;
vector<int> br;
void init(signed N, signed A[], signed B[]) {
	n=N; ar=br=vector<int>(n);
	students=vector<pair<int,int>>(n);
	for (int i=0; i<n; i++) {
		ar[i] = A[i]; br[i] = B[i];
		students[i] = {A[i],B[i]};
	}
	sort(students.begin(), students.end(), [&](const pair<int,int> &p1, const pair<int,int> &p2) {
		return p1.first<p2.first;
	});
}

signed can(signed M, signed K[]) {
	auto comp = [&](pair<int,int> s1, pair<int,int> s2) {return s1.second<s2.second;};	
	multiset<pair<int,int>,decltype(comp)> cur(comp);
	int m = M;
	vector<int> kvals;
	for (int i=0; i<m; i++) {
		kvals.push_back(K[i]);
	}
	sort(kvals.begin(), kvals.end());
	map<int,int> need;
	for (auto i:kvals) {
		need[i]+=i;
	}
	vector<vector<int>> req;
	for (auto i:need) {
		req.push_back({i.first,i.second});
	}
	sort(req.begin(), req.end());
	int cpointer = 0;
	int pointer = 0; 
	while (pointer<req.size() && cpointer<students.size() && students[cpointer].first<=req[pointer][0]) {
		cur.insert(students[cpointer]);
		cpointer++;
	}
	signed work = 0;
	while (cur.size()) {
		pair<int,int> student = *cur.begin(); 
		if (pointer==req.size()) {
			work=1;
			break;
		}
		if (student.first>req[pointer][0]) {
			assert(false);
			continue;
		}
		if (student.second<req[pointer][0]) {
			cur.erase(cur.find(student));
			continue;
		}
		cur.erase(cur.find(student));
		if (debug) cout << "prereduced " << pointer <<" " << req[pointer][0] <<" " << req[pointer][1] << endl;
		if (debug) cout << "with " << student.first <<" " << student.second << endl;
		req[pointer][1]--; 

		if (debug) cout << "reduced " << pointer <<" " << req[pointer][0] <<" " << req[pointer][1] << endl;
		if (debug) cout << endl;
		if (req[pointer][1]==0) {
			pointer++;
			while (pointer<req.size() && cpointer<students.size() && students[cpointer].first<=req[pointer][0]) {
				cur.insert(students[cpointer]);
				cpointer++;
			}
		}
	}
	//if (debug) cout << "finished " << pointer <<" " << req.size() <<" " << req[pointer][0] <<" " << req[pointer][1] << endl;
	if (pointer==req.size()) {
		work=1;
	}
	return work;
}

Compilation message (stderr)

teams.cpp: In function 'int can(int, int*)':
teams.cpp:43:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |  while (pointer<req.size() && cpointer<students.size() && students[cpointer].first<=req[pointer][0]) {
      |         ~~~~~~~^~~~~~~~~~~
teams.cpp:43:39: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |  while (pointer<req.size() && cpointer<students.size() && students[cpointer].first<=req[pointer][0]) {
      |                               ~~~~~~~~^~~~~~~~~~~~~~~~
teams.cpp:50:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |   if (pointer==req.size()) {
      |       ~~~~~~~^~~~~~~~~~~~
teams.cpp:71:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |    while (pointer<req.size() && cpointer<students.size() && students[cpointer].first<=req[pointer][0]) {
      |           ~~~~~~~^~~~~~~~~~~
teams.cpp:71:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |    while (pointer<req.size() && cpointer<students.size() && students[cpointer].first<=req[pointer][0]) {
      |                                 ~~~~~~~~^~~~~~~~~~~~~~~~
teams.cpp:78:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |  if (pointer==req.size()) {
      |      ~~~~~~~^~~~~~~~~~~~

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