Submission #589954

#	Time	Username	Problem	Language	Result	Execution time	Memory
589954		FatihSolak	Teams (IOI15_teams)	C++17	21 / 100	598 ms	524288 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
#define N 500005
using namespace std;
int n;
multiset<int> s[N];
vector<int> tmp[N];
void init(int n_, int a[], int b[]) {
	n = n_;
	for(int i = 0;i<n;i++){
		tmp[a[i]].push_back(b[i]);
	}
	for(int i = 0;i<n;i++){
		s[0].insert(n+1);
	}
	for(int i = 1;i<=n;i++){
		s[i] = s[i-1];
		for(auto u:tmp[i]){
			s[i].insert(u);
		}
		while(s[i].size() && *s[i].begin() < i){
			s[i].erase(s[i].begin());
		}
	}
}
pair<int,int> val[N];
int can(int m, int k[]) {
	map<int,int> mp;
	sort(k,k+m);	
	long long sum = 0;
	for(int i = 0;i<m;i++){
		sum += k[i];
		mp[k[i]]++;
	}
	if(sum > n)return 0;
	vector<pair<int,int>> v;
	for(auto u:mp){
		v.push_back(u);
	}
	for(int x = 0;x<v.size();x++){
		int needed = v[x].first * v[x].second;
		int del = v[x].first-1;
		int tot = 0;
		for(int i = v[x].first;i<=n+1;i++){
			int nwcount = s[v[x].first].count(i);
			int delcount = 0;
			for(int j = 0;j<x;j++){
				if(val[v[j].first].first + 1 < i)continue;
				int nwdel = s[v[j].first].count(i);
				if(val[v[j].first].first + 1 == i){
					delcount += val[v[j].first].second;
					continue;
				}
				else delcount = nwdel;
			}
			nwcount -= delcount;
			if(tot + nwcount <= needed){
				del++;
				tot += nwcount;
			}
			else break;
		}
		val[v[x].first] = {del,needed-tot};
		if(val[v[x].first].first == n && val[v[x].first].second)return 0;
	}
	return 1;
}

Compilation message (stderr)

teams.cpp: In function 'int can(int, int*)':
teams.cpp:40:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |  for(int x = 0;x<v.size();x++){
      |                ~^~~~~~~~~
teams.cpp:45:37: warning: conversion from 'std::multiset<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   45 |    int nwcount = s[v[x].first].count(i);
      |                  ~~~~~~~~~~~~~~~~~~~^~~
teams.cpp:49:36: warning: conversion from 'std::multiset<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   49 |     int nwdel = s[v[j].first].count(i);
      |                 ~~~~~~~~~~~~~~~~~~~^~~

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