| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 586718 | MDario | 로봇 (IOI13_robots) | C++11 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "robots.h"
#include<bits/stdc++.h>
int f(int xf[], int yf){
if(xf[yf]==yf)return yf;
else return xf[yf]=f(xf, xf[yf]);
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int s[]) {
vector<int> x, y;
for(int i=0; i<A; i++)x.push_back(X[i]);
x.push_back(0);
for(int i=0; i<B; i++)y.push_back(Y[i]);
y.push_back(0);
sort(x, x+A);
sort(y, y+B);
pair<int, int> a[T];
int l, r, m, b[T], b1[A+2], b2[B+2], nexa[A+2], nexb[B+2], c[20];
for(int i=0; i<T; i++){
l=0;
r=A+1;
while(l+1<r){
m=(l+r)/2;
if(w[i]>x[m])l=m;
else r=m;
}
a[i].F=r;
l=0;
r=B+1;
while(l+1<r){
m=(l+r)/2;
if(s[i]>y[m])l=m;
else r=m;
}
a[i].S=r;
}
sort(a, a+T);
l=-1;
r=T+1;
while(l+1<r){
m=(l+r)/2;
c[1]=0;
for(int i=0; i<T; i++)b[i]=0;
for(int i=0; i<=A; i++){
b1[i]=0;
nexa[i]=i;
}
b1[A+1]=m;
nexa[A+1]=A+1;
for(int i=0; i<=B; i++){
b2[i]=0;
nexb[i]=i;
}
b2[B+1]=m;
nexb[B+1]=B+1;
for(int i=T-1; i>=0; i--){
c[0]=f(nexb, a[i].S);
if(c[0]!=B+1){
b[i]=1;
b2[c[0]]++;
if(b2[c[0]]==m)nexb[c[0]]=c[0]+1;
}
}
for(int i=0; i<T; i++){
if(!b[i]){
c[0]=f(nexa, a[i].F);
if(c[0]!=A+1){
b1[c[0]]++;
if(b1[c[0]]==m)nexa[c[0]]=c[0]+1;
}
else c[1]=1;
}
}
if(!c[1])r=m;
else l=m;
}
if(r==T+1)return -1;
return r;
}