| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 287467 | AMO5 | 로봇 (IOI13_robots) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "robots.h"
using namespace std;
#define fi first
#define se second
#define sz(x) (int)x.size()
using ii = pair<int,int>;
const int mxn = 1e6+5;
int w[mxn],s[mxn],n;
bool works(int tar, int x[], int a, int y[], int b, bool sw){
if(a==0)return;
priority_queue<ii,vector<ii>,greater<ii>>pq,pq2;
for(int i=0; i<n; i++){
if(!sw)pq.emplace(w[i],s[i]);
else pq.emplace(s[i],w[i]);
}
//cerr<<tar<<": \n";
for(int i=0; i<a; i++){
int cnt = 0;
//cerr<<i<<"--"<<x[i]<<": ";
while(cnt<tar){
if(!pq.empty()&&pq.top().fi<x[i]){
//cerr<<"["<<pq.top().fi<<","<<pq.top().se<<"]"<<" "<<cnt+1<<" ";
pq.pop();
cnt++;
}else break;
}
//cerr<<"\n";
}
while(sz(pq)){
pq2.emplace(pq.top().se,pq.top().fi);
pq.pop();
}
for(int i=0; i<b; i++){
int cnt = 0;
//cerr<<i<<"- "<<y[i]<<": ";
while(cnt<tar){
if(!pq2.empty()&&pq2.top().fi<y[i]){
//cerr<<"["<<pq2.top().fi<<","<<pq2.top().se<<"]"<<" "<<cnt+1<<" ";
pq2.pop();
cnt++;
}else break;
}
//cerr<<"\n";
}
return sz(pq2)==0;
}
int putaway(int A,int B,int T, int X[],int Y[],int W[],int S[]){
sort(X,X+A);
sort(Y,Y+B);
n=T;
for(int i=0; i<T; i++){
w[i]=W[i],s[i]=S[i];
if(w[i]>=X[A-1]&&s[i]>=Y[B-1]){
//cerr<<"dead "<<w[i]<<" "<<s[i]<<" "<<X[A-1]<<" "<<Y[B-1]<<"\n";
return -1;
}
}
int lo = 1, hi = T, ans = T;
while(lo<=hi){
int mid=(lo+hi)/2;
if(works(mid,X,A,Y,B,0)||works(mid,Y,B,X,A,1)){
hi=mid-1;
ans = mid;
}else{
lo=mid+1;
}
}
return ans;
}
/*
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n2,m2,t2; cin>>n2>>m2>>t2;
int x2[n2],y2[m2],w2[t2],s2[t2];
for(int i=0; i<n2; i++)cin>>x2[i];
for(int i=0; i<m2; i++)cin>>y2[i];
for(int i=0; i<t2; i++)
cin>>w2[i]>>s2[i];
cout<<putaway(n2,m2,t2,x2,y2,w2,s2)<<endl;
return 0;
}
// */
//check for -1 both w[i]&s[i] exceed largest x[i]&y[i]