Submission #897922

#	Time	Username	Problem	Language	Result	Execution time	Memory
897922		Jawad_Akbar_JJ	Robots (IOI13_robots)	C++17	0 / 100	1 ms	4696 KiB

robots

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

using namespace std;
const int N = 1001;

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

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));

	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;
			ind--;

			while (i<t){
				part[1000].insert(v[i].second);
				i++;
			}
			break;
		}
		part[ind].insert(v[i].second);
	}


	sort(y,y + b);

	for (int i=0;i<=ind;i++)
		resp[i] = i;
	int erased = 0;
	int tm = 0;
	while (erased < t){
		tm++;
		bool er = false;
		for (int i=0;i<b;i++){
			for (int j=1000;j>=0;j--){
				if (part[j].size()==0)
					continue;
				auto u = part[j].upper_bound(y[i]-1);
				if (u==begin(part[j]))
					continue;
				u = prev(u);
				erased++;
				er = true;
				// cout<<"round "<<tm<<" from part["<<j<<"] "<<y[i]<<" erased "<<*u<<endl;
				part[j].erase(u);
				break;
			}
		}

		for (int i=ind;i>=0;i--){
			while (resp[i]>-1 and part[resp[i]].size()==0)
				resp[i]--;
			if (resp[i]==-1)
				continue;
			int k = resp[i];
			part[k].erase(prev(end(part[k])));
			er = true;
			erased++;
			// cout<<"round "<<tm<<" from part["<<k<<"] "<<x[i]<<" erased last"<<endl;
		}
		if (!er)
			return -1;
		// cout<<
	}
	return tm;

	



}

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