| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 87997 | Pajaraja | Robots (IOI13_robots) | C++17 | 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 "grader.h"
#include <bits/stdc++.h>
using namespace std;
int a,b,t,x[50020],y[50020],nxt[50020],prv[50020],cnt[50020];
bool frsee[50020];
struct igracka{int w,s;};
bool cmp (igracka a,igracka b) {return a.w>b.w;}
igracka r[1000000];
int binary(int l,int d,int val)
{
if(l==d) return l;
int s=(l+d)/2;
if(y[s]>val) return binary(l,s,val);
return binary(s+1,d,val);
}
int root(int u)
{
while(nxt[u]!=u)
{
nxt[u]=nxt[nxt[u]];
u=nxt[u];
}
return u;
}
void connect(int u,int v){nxt[root(u)]=root(v);}
bool provera(int k)
{
fill(cnt+1,cnt+b+2,k);
int p=0;
long long d=0;
for(int i=1;i<=b+1;i++) nxt[i]=i;
for(int i=0;i<t;i++)
{
while(x[p+1]>r[i].w)
{
p++;
d+=k;
}
int tr=binary(1,b+1,r[i].s);
int w=root(tr);
if(w==b+1)
{
d--;
if(d<0) return false;
continue;
}
cnt[w]--;
if(cnt[w]==0) connect(w,w+1);
}
return true;
}
int binarna(int l,int d)
{
if(l==d)
{
if(l<=t) return l;
else return -1;
}
int s=(l+d)/2;
if(provera(s)) return binarna(l,s);
return binarna(s+1,d);
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[])
{
a=A;
b=B;
t=T;
for(int i=1;i<=a;i++) x[i]=-X[i-1];
for(int i=1;i<=b;i++) y[i]=Y[i-1];
for(int i=0;i<t;i++) r[i].s=S[i];
for(int i=0;i<t;i++) r[i].w=W[i];
sort(x+1,x+a+1);
sort(y+1,y+b+1);
x[0]=y[b+1]=2000000010;
y[0]=0;
for(int i=1;i<=a;i++) x[i]=-x[i];
sort(r,r+t,cmp);
return binarna(1,t+1);
}