Submission #897938

#	Time	Username	Problem	Language	Result	Execution time	Memory
897938		Faisal_Saqib	Robots (IOI13_robots)	C++17	39 / 100	3088 ms	26312 KiB

robots

#include "robots.h"
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const int N=3e6+100;
int deg[N];
int in_deg[N];
bool compaa(int a,int b)
{
	return (in_deg[a]<=in_deg[b]);
}
int putaway(int a, int b, int t, int x[], int y[], int w[], int s[])
{
	// We take a 
	std::vector<pair<int,int>> heavy_logic;
	for(int i=0;i<a;i++)
		heavy_logic.push_back({x[i],0});
	for(int i=0;i<b;i++)
		heavy_logic.push_back({0,y[i]});
	for(int i=0;i<t;i++)
		heavy_logic.push_back({w[i],s[i]});
	// for A vertex 0,1,..,a-1
	// For B vertex a,a+1,..,a+b-1
	// For t vertex a+b,a+b+1,..,a+b+t-1
	// cout<<"as\n";
	// for(auto [q,p]:heavy_logic)
	// {
	// 	cout<<q<<' '<<p<<endl;
	// }
	int ans=0;
	vector<int> amp;
	for(int j=(a+b);j<heavy_logic.size();j++)
	{
		for(int i=0;i<(a+b);i++)
		{
			if(heavy_logic[i].first>heavy_logic[j].first or heavy_logic[i].second>heavy_logic[j].second)
			{
				in_deg[j]++;
			}
		}
		if(in_deg[j]==0)
			return -1;
		amp.push_back(j);
	}
	sort(begin(amp),end(amp),compaa);
	for(auto j:amp)
	{
		int mi=1e9;
		int v=-1;
		for(int i=0;i<a+b;i++)
		{
			if(heavy_logic[i].first>heavy_logic[j].first or heavy_logic[i].second>heavy_logic[j].second)
			{
				if(deg[i]<mi)
				{
					mi=deg[i];
					v=i;
				}
			}
		}
		deg[v]++;
		ans=max(ans,deg[v]);
	}
	return ans;
}

Compilation message (stderr)

robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:33:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  for(int j=(a+b);j<heavy_logic.size();j++)
      |                  ~^~~~~~~~~~~~~~~~~~~

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