Submission #198996

#	Time	Username	Problem	Language	Result	Execution time	Memory
198996		maximath_1	Robots (IOI13_robots)	C++11	0 / 100	423 ms	26764 KiB

robots

#include"robots.h"
#include<bits/stdc++.h>
using namespace std;
#define int 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++){
		int siz=vv[i].size();
		for(int j=0; j<siz; j++)
			pq.push(vv[i][j]);
		if(sisa>=siz-x) sisa+=x-siz;
		else{
			for(int j=1; j<=siz-x-sisa; j++){
				if(pq.empty()) return false;
				isi.push_back(pq.top()); pq.pop();
			}
			sisa=0;
		}
	}
	sort(isi.begin(), isi.end());
	for(int i=0; i<isi.size(); i++){
		int tmp=i/x+1;
		if(tmp>b || tmp>isi[i]) return false;
	}
	return true;
}
int32_t putaway(int32_t _a, int32_t _b, int32_t _t, int32_t x[], int32_t y[], int32_t w[], int32_t 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]=make_pair(w[i], s[i]);
	for(int i=0; i<n; i++){
		int l=0, r=a-1, md, wt, sz;
		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(long long int)':
robots.cpp:12:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<vv[0].size(); i++)
               ~^~~~~~~~~~~~~
robots.cpp:28:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<isi.size(); i++){
               ~^~~~~~~~~~~

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