Submission #1036354

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036354		MSK17	Robots (IOI13_robots)	C++17	76 / 100	3088 ms	42420 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>

int putaway(int a, int b, int t, int X[], int Y[], int w[], int s[]) {
    std::vector<std::pair<int,int>> toys(t);
	std::vector<int> x(a), y(b);
	for(int i{}; i < a; ++i)
		x[i]=X[i];
	for(int i{}; i < b; ++i)
		y[i]=Y[i];
	std::sort(x.begin(), x.end());
	std::sort(y.begin(), y.end());
	for(int i{}; i < t; ++i){
		toys[i].first=w[i];
		toys[i].second=s[i];
	}
	std::sort(toys.begin(), toys.end());
	for(int i{}; i < t; ++i){
		if((a==0||toys[i].first>=x[a-1])&&(b==0||toys[i].second>=y[b-1]))
			return -1;
	}
	int l=0, r=t;
	while(r-l>1){
		int m=(l+r)/2;
		int cur=0;
		std::multiset<int> st;
		for(int i{}; i < a; ++i){
			while(cur<toys.size()&&toys[cur].first<x[i]){
				st.insert(toys[cur].second);
				++cur;
			}
			for(int j{}; j < m; ++j){
				if(st.size()>0){
					int max=*(st.rbegin());
					st.erase(st.find(max));
				}
				else break;
			}
		}
		while(cur<toys.size()){
			st.insert(toys[cur].second);
			++cur;
		}
		for(int i{}; i < b; ++i){
			for(int j{}; j < m; ++j){
				if(st.size()==0)
					break;
				int min=*(st.begin());
				if(min<y[i])
					st.erase(st.find(min));
				else break;
			}
		}
		if(st.size()==0)
			r=m;
		else
			l=m;
	}
	return r;
}

Compilation message (stderr)

robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:28:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |    while(cur<toys.size()&&toys[cur].first<x[i]){
      |          ~~~^~~~~~~~~~~~
robots.cpp:40:12: 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 |   while(cur<toys.size()){
      |         ~~~^~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 0 / 14
• Subtask 3: 25 / 25
• Subtask 4: 37 / 37
• Subtask 5: 0 / 10