Submission #115490

#	Time	Username	Problem	Language	Result	Execution time	Memory
115490		faustaadp	Robots (IOI13_robots)	C++17	100 / 100	1024 ms	65536 KiB

robots

#include "robots.h"
#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll i,atas[1010101],bawah[1010101],has,A,B,n;
pair<ll,ll> Z[1010101];
vector<ll> isi[1010101];
ll cek(ll aa)
{
	ll ii,jj,te=A,sisa=0;
	vector<ll> tom;
	priority_queue<ll> pq;
	for(ii=0;ii<isi[0].size();ii++)
		tom.pb(isi[0][ii]);
	for(ii=1;ii<=A;ii++)
	{
		for(jj=0;jj<isi[ii].size();jj++)
			pq.push(isi[ii][jj]);
		ll sz=isi[ii].size();
		if(sz<=(aa+sisa))
			sisa=(aa+sisa)-sz;
		else
		{
			for(jj=1;jj<=(sz-(aa+sisa));jj++)
			{
				if(pq.empty())return 0;
				tom.pb(pq.top());
				pq.pop();
			}
			sisa=0;
		}
	}
	sort(tom.begin(),tom.end());
	//if(aa==2)
	//for(i=0;i<tom.size();i++)
	//	cout<<i<<" "<<tom[i]<<"\n";
	for(i=0;i<tom.size();i++)
	{
		ll tem=i/aa+1;
		if(tem>B||tem>tom[i])return 0;
	}	
	//cout<<aa<<"\n";
	return 1;
}
int putaway(int Axa, int Bxa, int T, int X[], int Y[], int W[], int S[]) 
{
	n=T;
	A=Axa;
	B=Bxa;
	sort(X,X+A);
	sort(Y,Y+B);
	for(i=0;i<T;i++)
		Z[i]=mp(W[i],S[i]);
	//sort(Z,Z+T);
	//reverse(Z,Z+T);
	for(i=0;i<T;i++)
	{
		ll L=0,R=A-1,C;
		while(L<=R)
		{
			C=(L+R)/2;
			if(Z[i].fi<X[C])
			{
				atas[i]=A-C;
				R=C-1;
			}
			else
				L=C+1;
		}
		L=0,R=B-1,C;
		while(L<=R)
		{
			C=(L+R)/2;
			if(Z[i].se<Y[C])
			{
				bawah[i]=B-C;
				R=C-1;
			}
			else
				L=C+1;
		}
		isi[atas[i]].pb(bawah[i]);
	}
	has=-1;
	ll L=1,R=T,C;
	while(L<=R)
	{
		C=(L+R)/2;
		if(cek(C))
		{
			has=C;
			R=C-1;
		}
		else
			L=C+1;
	}
	return has;
	for(i=0;i<T;i++)cout<<atas[i]<<" ";cout<<"\n";
	for(i=0;i<T;i++)cout<<bawah[i]<<" ";cout<<"\n";
}

Compilation message (stderr)

robots.cpp: In function 'll cek(ll)':
robots.cpp:17:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ii=0;ii<isi[0].size();ii++)
           ~~^~~~~~~~~~~~~~
robots.cpp:21:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(jj=0;jj<isi[ii].size();jj++)
            ~~^~~~~~~~~~~~~~~
robots.cpp:41:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<tom.size();i++)
          ~^~~~~~~~~~~
robots.cpp:14:11: warning: unused variable 'te' [-Wunused-variable]
  ll ii,jj,te=A,sisa=0;
           ^~
robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:74:14: warning: right operand of comma operator has no effect [-Wunused-value]
   L=0,R=B-1,C;
              ^
robots.cpp:102:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for(i=0;i<T;i++)cout<<atas[i]<<" ";cout<<"\n";
  ^~~
robots.cpp:102:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for(i=0;i<T;i++)cout<<atas[i]<<" ";cout<<"\n";
                                     ^~~~
robots.cpp:103:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for(i=0;i<T;i++)cout<<bawah[i]<<" ";cout<<"\n";
  ^~~
robots.cpp:103:38: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for(i=0;i<T;i++)cout<<bawah[i]<<" ";cout<<"\n";
                                      ^~~~

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