Submission #897980

#	Time	Username	Problem	Language	Result	Execution time	Memory
897980		Jawad_Akbar_JJ	Robots (IOI13_robots)	C++17	14 / 100	146 ms	19136 KiB

robots

#include <iostream>
#include <vector>
#include <set>
#include <cassert>
#include <algorithm>
#include "robots.h"

using namespace std;
const int N = 50000 + 10;

multiset<int> part[N];
int resp[N];
int sz[N];

bool valid(int k,int ind){
	int sum = 0;
	for (int i=0;i<=ind;i++){
		sum += sz[i];
		int kk = min(sum,k);
		sum -= kk;
		// if (k==3)
		// 	cout<<i<<" j "<<sum + kk - sz[ind]<<" "<<sz[ind]<<" "<<kk<<endl;
	}
	return (sum == 0);
}

int putaway(int a,int b,int t,int x[],int y[],int w[],int s[]){
	vector<pair<int,int>> v;

	for (int i=0;i<t;i++)
		v.push_back({w[i],s[i]});

	sort(begin(v),end(v));

	if (t==2 and a + b == 2){
		if (a==1 and b==1){
			if (w[0]<x[0] and s[1]<y[0])
				return 1;
			if (w[1]<x[0] and s[0]<y[0])
				return 1;
			if (max(w[0],w[1]) < x[0])
				return 2;
			if (max(s[0],s[1]) < y[0])
				return 2;
			return -1;
		}
		if (a==2){
			sort(w,w + t);
			sort(x,x + t);
			if (x[0]>w[0] and x[1]>w[1])
				return 1;
			if (x[1]>w[1])
				return 2;
			return -1;
		}
		else{
			sort(s,s + t);
			sort(y,y + t);
			if (y[0]>s[0] and y[1]>s[1])
				return 1;
			if (y[1]>s[1])
				return 2;
			return -1;
		}
	}



	sort(x,x + a);
	
	int ind = 0;
	
	for (int i=0;i<t;i++){
		while (ind < a and v[i].first >= x[ind])
			ind++;
		if (ind == a){
			if (b==0)
				return -1;
		}
		sz[ind]++;
	}


	int l = 1,r = t;

	while (l + 1 < r){
		int mid = (l + r)/2;
		// cout<<mid<<" ";
		if (valid(mid,ind))
			r = mid;
		else
			l = mid;
		// cout<<l<<" "<<r<<endl;
	}
	if (valid(l,ind))
		r = l;
	return r;



}

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