| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 262849 | uacoder123 | Robots (IOI13_robots) | C++14 | 0 ms | 0 KiB |
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 <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define mp(i,a) make_pair(i,a)
#define pb(a) push_back(a)
#define bit(x,b) (x&(1LL<<b))
typedef pair <int,int> ii;
typedef pair <int,ii> iii;
typedef vector <int> vi;
int t,a,b;
vector<ii> v;
vi v1,v2,v4;
multiset<int> s;
bool cmp(ii a,ii b)
{
return a.S<b.S;
}
int check(int m)
{
int j=0,pj=-1;
for(int i=0;i<a;++i)
{
while(j!=t&&v[j].F<v1[i])
j++;
if(j!=0)
{
s.insert(v4.begin()+pj+1,v4.begin()+j);
pj=j;
}
int co=0;
while(co!=m&&s.size())
{
s.erase(((--s.end())));
co++;
}
}
if(pj<t-1)
{
s.insert(v4.begin()+pj+1,v4.end());
}
for(int i=0;i<b;++i)
{
int co=0;
if(!s.size())
return 1;
while(co!=m&&s.size()&&(*s.begin())<v2[i])
{
s.erase((s.begin()));
co++;
}
}
if(s.size())
return 0;
return 1;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[])
{
t=T;
a=A;
b=B;
for(int i=0;i<a;++i)
v1.pb(X[i]);
for(int i=0;i<b;++i)
v2.pb(Y[i]);
for(int i=0;i<t;++i)
v.pb(mp(W[i],S[i]));
sort(all(v));
sort(all(v1));
sort(all(v2));
int la=-1;
for(int i=0;i<a;++i)
{
auto it=lower_bound(all(v),mp(v[i].F,0))-v.begin();
it--;
if(it!=la)
{
sort(v.begin()+la+1,v.begin()+it+1,cmp);
la=it;
}
}
if(la!=t-1)
sort(v.begin()+la+1,v.end(),cmp);
for(int i=0;i<t;++i)
v4.pb(v[i].S);
int ma=0;
for(int i=t-1;i>=0;--i)
{
if(v1.size()&&(v[i].F<v1.back()))
break;
else
ma=max(v[i].S,ma);
}
if(v2.size()&&ma>=v2.back())
return -1;
int l=(t)/(a+b),r=t,ans=t;
while(l<=r)
{
int m=(l+r)/2;
s.clear();
if(check(m))
{
r=m-1;
ans=m;
}
else
l=m+1;
}
return ans;
}