Submission #198998

#	Time	Username	Problem	Language	Result	Execution time	Memory
198998		maximath_1	Robots (IOI13_robots)	C++11	76 / 100	284 ms	13036 KiB

robots

#include"robots.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n, a, b;
vector<pair<int, int> >v;
vector<int>vv[50005];
bool ok(int x){
	int sisa=0;
	vector<int>isi;
	priority_queue<int>pq;
	for(int i=0; i<vv[0].size(); i++)
		isi.push_back(vv[0][i]);
	for(int i=1; i<=a; i++){
	//	cout<<sisa<<"->";
		for(int j=0; j<(int)vv[i].size(); j++)
			pq.push(vv[i][j]);
		int siz=vv[i].size();
		if(sisa>=siz-x) sisa-=siz-x;
		else{
			for(int j=1; j<=siz-x-sisa; j++){
				if(pq.empty()) return false;
				isi.push_back(pq.top()); pq.pop();
			}
			sisa=0;
		}
	//	cout<<sisa<<endl;
	}
	sort(isi.begin(), isi.end());
	for(int i=0; i<(int)isi.size(); i++){
		int tmp=i/x+1;
		if(tmp>b || tmp>isi[i]) return false;
	}
	return true;
}
int putaway(int _a, int _b, int _t, int x[], int y[], int w[], int s[]){
	n=_t;
	a=_a; b=_b;
	sort(x, x+a); sort(y, y+b);
	v.resize(n);
	for(int i=0; i<n; i++)
		v[i]={w[i], s[i]};
	for(int i=0; i<n; i++){
		int l=0, r=a-1, md;
		int wt=0, sz=0;
		while(l<=r){
			md=(l+r)/2;
			if(v[i].first<x[md]){
				wt=a-md;
				r=md-1;
			}else l=md+1;
		}
		l=0, r=b-1;
		while(l<=r){
			md=(l+r)/2;
			if(v[i].second<y[md]){
				sz=b-md;
				r=md-1;
			}else l=md+1;
		}
		vv[wt].push_back(sz);
	}
	int ans=-1;
	int l=1, r=n, md;
	while(l<=r){
		md=(l+r)/2;
		if(ok(md)){
			ans=md; r=md-1;
		}else l=md+1;
	}
	return ans;
}

Compilation message (stderr)

robots.cpp: In function 'bool ok(int)':
robots.cpp:12:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<vv[0].size(); i++)
               ~^~~~~~~~~~~~~

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