| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 67225 | Vahan | 로봇 (IOI13_robots) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "robots.h"
#include<set>
#include<vector>
#include<cstdio>
#include<string>
#include<algorithm>
#include<iostream>
using namespace std;
vector<pair<int,int> > v;
multiset<int> se;
int a,b,t,x[2000000],y[2000000],w[2000000],s[2000000];
int kar(int p)
{
se.clear();
for(int i=0;i<t+a;i++)
{
int e=v[i].first;
int f=v[i].second;
if(f==-1)
{
int u=0;
set<int>::iterator it;
while(se.size()>0 && u<p)
{
u++;
it=se.end();
it--;
se.erase(it);
}
}
else
se.insert(f);
}
for(int i=0;i<b;i++)
{
int u=0;
while(se.size()>0 && (*se.begin())<y[i] && u<p)
{
se.erase(se.begin());
u++;
}
}
if(se.size()==0)
return 1;
else
return 0;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
memcpy(x,X,A*sizeof(int));
memcpy(y,Y,B*sizeof(int));
memcpy(w,W,T*sizeof(int));
memcpy(s,S,T*sizeof(int));
a=A;
b=B;
t=T;
sort(x,x+a);
sort(y,y+b);
for(int i=0;i<T;i++)
v.push_back(make_pair(w[i],s[i]));
for(int i=0;i<a;i++)
v.push_back(make_pair(x[i],-1));
sort(v.begin(),v.end());
int l=1,r=T;
while(l!=r)
{
int mid=(l+r)/2;
if(kar(mid))
r=mid;
else
l=mid+1;
}
if(kar(l))
return l;
else
return -1;
}