# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
222910 | laoriu | 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>
#include "robots.h"
using namespace std;
typedef pair <int,int> pp;
pp A[1000002];
int pos[1000002],nextt[100002],C[100002];
int dsu[100002],val[100002];
int root(int u)
{
int v=u;
while (dsu[u]>=0) u=dsu[u];
while (dsu[v]>=0)
{
int p=dsu[v];
dsu[v]=u;
v=p;
}
return u;
}
int unionn(int u,int v)
{
if (dsu[u]>dsu[v]) swap(u,v);
dsu[u]+=dsu[v];dsu[v]=u;
val[u]=max(val[u],val[v]);
}
int check(int a,int b,int n,int X[],int Y[],int k)
{
for (int i=0;i<=b;i++)
{
C[i]=0;
dsu[i]=-1;val[i]=i;
// assert(root(val[i])==i);
}
vector <int> P;
//cout<<"cac "<<k<<endl;
for (int i=n-1;i>=0;i--)
{
int p=pos[i];
p=root(p);
if (val[p]==b) P.push_back(A[i].first);
else
{
int x=val[p];
assert(C[x]<k);
//if (C[x]>=k) cerr<<p<<' '<<x<<endl;
C[x]++;
if (C[x]==k)
{
unionn(p,root(x+1));
int u=root(p);
assert(val[u]>=x+1);
// assert(root(x)==root(x+1));
}
}
}
for (int i=0;i<P.size();i+=k)
if (i/k>=a||P[i]>X[i/k]) return 0;
return 1;
}
int putaway(int a,int b,int n,int X[],int Y[],int W[],int S[])
{
sort(X,X+a,greater<int>());sort(Y,Y+b);
for (int i=0;i<n;i++)
{
W[i]++;S[i]++;
A[i].first=W[i];
A[i].second=S[i];
}
sort(A,A+n);
for (int i=0;i<n;i++)
{
int d=0;int c=b-1;
pos[i]=b;
while (d<=c)
{
int mid=(d+c)/2;
if (Y[mid]>=A[i].second) {pos[i]=mid;c=mid-1;}
else d=mid+1;
}
// cout<<A[i].first<<' '<<A[i].second<<' '<<pos[i]<<endl;
}
int d=1;int c=n;int res=-1;
while (d<=c)
{
int mid=(d+c)/2;
if (check(a,b,n,X,Y,mid)) {res=mid;c=mid-1;}
else d=mid+1;
}
return res;
}
/*int main()
{
freopen("robotz.inp","r",stdin);
freopen("robotz.out","w",stdout);
int a,b,n,X[50002],Y[50002],W[1000002],S[1000002];
cin>>a>>b>>n;
for (int i=0;i<a;i++) cin>>X[i];
for (int i=0;i<b;i++) cin>>Y[i];
for (int i=0;i<n;i++) cin>>W[i]