This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXT=1e6+6;
const int MAXN=5e4+6;
struct toy
{
int w,s;
bool operator<(const toy &other)const
{
if(w!=other.w)return w<other.w;
return s>other.s;
}
};
vector<toy>toys;
vector<int>weak,small;
bool used[MAXT];
int fen[MAXT];
void update(int idx,int val)
{
idx++;
if(idx<=0)return;
for(;idx<MAXN;idx+=idx&(-idx))
{
fen[idx]+=val;
}
}
int query(int idx)
{
if(idx<0)return 0;
idx++;
int ret=0;
for(;idx>0;idx-=idx&(-idx))
{
ret+=fen[idx];
}
return ret;
}
bool ok(int moves)
{
memset(used,0,sizeof(used));
memset(fen,0,sizeof(fen));
for(int i=0;i<small.size();i++)update(i,moves);
for(int i=0;i<toys.size();i++)
{
int s=toys[i].s;
int low1=0,high1=small.size()-1,mid1,best1=-1;
while(low1<=high1)
{
mid1=(low1+high1)/2;
if(small[mid1]>=s)
{
best1=mid1;
low1=mid1+1;
}
else high1=mid1-1;
}
int j=best1;
if(query(j)<=0)
{
continue;
}
else
{
used[i]=1;
update(j,-1);
}
}
int cnt=moves,j=0;
for(int i=0;i<toys.size();i++)
{
if(used[i])continue;
if(j>=weak.size())return 0;
if(cnt==0&&j==weak.size()-1)return 0;
if(cnt==0)
{
cnt=moves;
j++;
}
if(toys[i].w>weak[j])return 0;
cnt--;
}
return 1;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
for(int i=0;i<T;i++)
{
toys.push_back({W[i],S[i]});
}
sort(toys.rbegin(),toys.rend());
for(int i=0;i<A;i++)weak.push_back(X[i]-1);
for(int i=0;i<B;i++)small.push_back(Y[i]-1);
sort(weak.rbegin(),weak.rend());
for(int i=0;i<toys.size();i++)
{
int low=0,high=weak.size()-1,mid,best=-1;
while(low<=high)
{
mid=(low+high)/2;
if(weak[mid]>=toys[i].w)
{
best=mid;
low=mid+1;
}
else high=mid-1;
}
if(best!=-1)toys[i].w=weak[best];
else toys[i].w=2000000001;
}
sort(toys.rbegin(),toys.rend());
sort(small.rbegin(),small.rend());
int low=1,high=T,mid,best=T+1;
while(low<=high)
{
mid=(low+high)/2;
if(ok(mid))
{
best=mid;
high=mid-1;
}
else low=mid+1;
}
if(best==T+1)
{
return -1;
}
return best;
}
Compilation message (stderr)
robots.cpp: In function 'bool ok(int)':
robots.cpp:43:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for(int i=0;i<small.size();i++)update(i,moves);
| ~^~~~~~~~~~~~~
robots.cpp:44:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<toy>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | for(int i=0;i<toys.size();i++)
| ~^~~~~~~~~~~~
robots.cpp:70:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<toy>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | for(int i=0;i<toys.size();i++)
| ~^~~~~~~~~~~~
robots.cpp:73:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | if(j>=weak.size())return 0;
| ~^~~~~~~~~~~~~
robots.cpp:74:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | if(cnt==0&&j==weak.size()-1)return 0;
| ~^~~~~~~~~~~~~~~
robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:94:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<toy>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | for(int i=0;i<toys.size();i++)
| ~^~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |