Submission #164387

#	Time	Username	Problem	Language	Result	Execution time	Memory
164387		nafis_shifat	Robots (IOI13_robots)	C++14	100 / 100	2505 ms	28764 KiB

robots

#include "robots.h"
#include<bits/stdc++.h>
#define pii pair<int,int>
#define f first
#define s second
#define ll long long
using namespace std;
vector<pii> toy;
vector<int> wt;
vector<int> st;
bool can(int s)
{
	priority_queue<pii> pq;
	int pnt=0;
	for(int i=0;i<st.size();i++)
	{
		while(pnt<toy.size()&&toy[pnt].f<st[i])
		{
			pq.push({toy[pnt].s,toy[pnt++].f});
		}
		for(int j=0;j<s && !pq.empty();j++)
		{
			pq.pop();
		}
	}
	for(;pnt<toy.size();pnt++)pq.push({toy[pnt].s,toy[pnt].f});
	for(int i=wt.size()-1;i>=0;i--)
	{
		for(int j=0;j<s && !pq.empty() &&  pq.top().f<wt[i];j++)
		{
			pq.pop();
		}
	}
	return pq.empty();



}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    for(int i=0;i<T;i++)toy.emplace_back(S[i],W[i]);
    for(int i=0;i<A;i++)wt.push_back(X[i]);
    for(int i=0;i<B;i++)st.push_back(Y[i]);
    sort(toy.begin(), toy.end());
    sort(st.begin(),st.end());
    sort(wt.begin(),wt.end());
    int lo=1;
    int hi= T;
    int r=-1;
    while(lo<=hi)
    {
    	int mid=lo+hi>>1;
    	bool f=can(mid);
    	if(f)
    	{
    		hi=mid-1;
    		r=mid;
    	}
    	else
    	{
    		lo=mid+1;
    	}
    }
    return r;
    
}

Compilation message (stderr)

robots.cpp: In function 'bool can(int)':
robots.cpp:15:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<st.size();i++)
              ~^~~~~~~~~~
robots.cpp:17:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(pnt<toy.size()&&toy[pnt].f<st[i])
         ~~~^~~~~~~~~~~
robots.cpp:19:31: warning: operation on 'pnt' may be undefined [-Wsequence-point]
    pq.push({toy[pnt].s,toy[pnt++].f});
                            ~~~^~
robots.cpp:26:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(;pnt<toy.size();pnt++)pq.push({toy[pnt].s,toy[pnt].f});
       ~~~^~~~~~~~~~~
robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:51:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
      int mid=lo+hi>>1;
              ~~^~~

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