Submission #307182

#	Time	Username	Problem	Language	Result	Execution time	Memory
307182		vipghn2003	Robots (IOI13_robots)	C++14	100 / 100	787 ms	15736 KiB

robots

#include"robots.h"
#include<bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
using namespace std;

const int N=1e6+5;
int a,b,grS[N],grW[N],x[N],y[N],pW[N],pS[N],cntS[N],cntW[N];
vector<tuple<int,int,int>>order;

int FindS(int u)
{
    if(pS[u]==u) return u;
    return pS[u]=FindS(pS[u]);
}

void UnionS(int u,int v)
{
    u=FindS(u);
    v=FindS(v);
    if(u==v) return ;
    if(u>v) swap(u,v);
    pS[u]=v;
}

int FindW(int u)
{
    if(pW[u]==u) return u;
    return pW[u]=FindW(pW[u]);
}

void UnionW(int u,int v)
{
    u=FindW(u);
    v=FindW(v);
    if(u==v) return ;
    if(u>v) swap(u,v);
    pW[u]=v;
}

bool check(int lim)
{
    for(int i=0;i<=b;i++)
    {
        cntS[i]=lim;
        pS[i]=i;
    }
    for(int i=0;i<=a;i++)
    {
        cntW[i]=lim;
        pW[i]=i;
    }
    for(auto&x:order)
    {
        int w=get<0>(x);
        int s=get<1>(x);
        int id=get<2>(x);
        int go=FindS(grS[id]);
        if(go!=b)
        {
            cntS[go]--;
            if(cntS[go]==0) UnionS(go,go+1);
        }
        else
        {
            go=FindW(grW[id]);
            if(go==a) return false;
            cntW[go]--;
            if(cntW[go]==0) UnionW(go,go+1);
        }
    }
    return true;
}

int putaway(int A,int B,int T,int X[],int Y[],int W[],int S[])
{
    a=A,b=B;
    for(int i=0;i<A;i++) x[i]=X[i];
    sort(x,x+A);
    for(int i=0;i<B;i++) y[i]=Y[i];
    sort(y,y+B);
    order.resize(T);
    for(int i=0;i<T;i++)
    {
        order[i]=make_tuple(W[i],S[i],i);
        grS[i]=upper_bound(y,y+B,S[i])-y;
        grW[i]=upper_bound(x,x+A,W[i])-x;
    }
    sort(order.begin(),order.end());
    reverse(order.begin(),order.end());
    int l=1,r=T,res=-1;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(!check(mid)) l=mid+1;
        else
        {
            res=mid;
            r=mid-1;
        }
    }
    return res;
}

/*
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int a,b,t;
    cin>>a>>b>>t;
    int x[a],y[b],w[t],s[t];
    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<t;i++) cin>>w[i]>>s[i];
    cout<<putaway(a,b,t,x,y,w,s);
}
3 2 10
6 2 9
4 7
4 6
8 5
2 3
7 9
1 8
5 1
3 3
8 7
7 6
10 5
*/

Compilation message (stderr)

robots.cpp: In function 'bool check(int)':
robots.cpp:57:13: warning: unused variable 'w' [-Wunused-variable]
   57 |         int w=get<0>(x);
      |             ^
robots.cpp:58:13: warning: unused variable 's' [-Wunused-variable]
   58 |         int s=get<1>(x);
      |             ^

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