| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 262822 | uacoder123 | 로봇 (IOI13_robots) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "robots.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;
int check(int m)
{
int j=0;
multiset<int> s;
for(int i=0;i<a;++i)
{
while(j!=t&&v[j].F<v1[i])
{
s.insert(v[j].S);
j++;
}
int co=0;
while(co!=m&&s.size())
{
s.erase(((--s.end())));
co++;
}
}
while(j!=t)
{
s.insert(v[j].S);
j++;
}
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 ma=0;
for(int i=t-1;i>=0;--i)
{
if(v1.size()&&(v[i].F<v1.back()))
break;
else
ma=max(v1[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;
if(check(m))
{
r=m-1;
ans=m;
}
else
l=m+1;
}
return ans;
}