Submission #870443

#	Time	Username	Problem	Language	Result	Execution time	Memory
870443		HuyQuang_re_Zero	Robots (IOI13_robots)	C++14	100 / 100	1819 ms	48644 KiB

robots

#include <bits/stdc++.h>
#define ll long long
#define db long double
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x))
#define N 1000005
#include "robots.h"
using namespace std;
struct International_Olympiad_in_Informatics
{
    bool d[N];
    int posx[N],posy[N],a[50005],b[50005],x[N],y[N],n,m,sz,i;
    bool check(int k)
    {
        memset(d,0,sizeof(d));
        priority_queue <II> h;
        int j=1;
        for(i=1;i<=n;i++)
        {
            while(j<=sz && x[posx[j]]<=a[i]) h.push({ y[posx[j]],posx[j] }),j++;
            int box=k;
            while(box>0 && h.size()>0)
            {
                int u=h.top().snd; h.pop();
                box--;
                d[u]=1;
            }
        }

        int box=k;
        j=1;
        for(i=1;i<=sz;i++)
        {
            int u=posy[i];
            if(d[u]==1) continue;
            while(j<=m && (box==0 || b[j]<y[u])) j++,box=k;
            if(j>m) return 0;
            box--;
        }
        return 1;
    }
    int Work(int _n,int _m,int _sz,int _a[],int _b[],int _x[],int _y[])
    {
        n=_n; m=_m; sz=_sz;
        for(i=1;i<=n;i++) a[i]=_a[i-1],a[i]--;
        for(i=1;i<=m;i++) b[i]=_b[i-1],b[i]--;
        for(i=1;i<=sz;i++)
        {
            x[i]=_x[i-1]; y[i]=_y[i-1];
            posx[i]=posy[i]=i;
        }
        sort(posx+1,posx+sz+1,[&](int i,int j){ return x[i]<x[j]; });
        sort(posy+1,posy+sz+1,[&](int i,int j){ return y[i]<y[j]; });
        sort(a+1,a+n+1);
        sort(b+1,b+m+1);
        int l=1,r=sz;
        while(l<r)
        {
            int mid=(l+r)>>1;
            if(check(mid)==1) r=mid; else l=mid+1;
        }
        if(check(l)) return l;
        return -1;
    }
} IOI;


int putaway(int n,int m,int sz,int a[],int b[],int x[],int y[])
{
    return IOI.Work(n,m,sz,a,b,x,y);
}
/*
int main()
{
    freopen("robots.inp","r",stdin);
    freopen("robots.out","w",stdout);
    int n,m,sz;
    cin>>n>>m>>sz;
    int x[102],y[102],a[102],b[102];
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<m;i++) cin>>b[i];
    for(int i=0;i<sz;i++) cin>>x[i];
    for(int i=0;i<sz;i++) cin>>y[i];
    cout<<putaway(n,m,sz,a,b,x,y);
}
*/

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 25 / 25
• Subtask 4: 37 / 37
• Subtask 5: 10 / 10