Submission #307171

#	Time	Username	Problem	Language	Result	Execution time	Memory
307171		vipghn2003	Robots (IOI13_robots)	C++14	90 / 100	3076 ms	13688 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,t,x[N],y[N];
bool vis[N];
vector<tuple<int,int,int>>order;

bool check(int lim)
{
    for(int i=0;i<t;i++) vis[i]=false;
    multiset<pii>cur;
    for(int i=0;i<b;i++) cur.insert(mp(y[i],lim));
    for(auto&x:order)
    {
        int w=get<0>(x);
        int s=get<1>(x);
        int id=get<2>(x);
        auto it=cur.upper_bound(mp(s,1e9));
        if(it!=cur.end())
        {
            vis[id]=true;
            pii tmp=*it;
            cur.erase(it);
            if(tmp.se!=1) cur.insert(mp(tmp.fi,tmp.se-1));
        }
    }
    cur.clear();
    for(int i=0;i<a;i++) cur.insert(mp(x[i],lim));
    for(auto&x:order)
    {
        int w=get<0>(x);
        int s=get<1>(x);
        int id=get<2>(x);
        if(vis[id]) continue;
        auto it=cur.upper_bound(mp(w,1e9));
        if(it==cur.end()) return false;
        pii tmp=*it;
        cur.erase(it);
        if(tmp.se!=1) cur.insert(mp(tmp.fi,tmp.se-1));
    }
    return true;
}

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=0;i<A;i++) x[i]=X[i];
    for(int i=0;i<B;i++) y[i]=Y[i];
    order.resize(T);
    for(int i=0;i<T;i++) order[i]=make_tuple(W[i],S[i],i);
    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);
}
*/
/*
2 1 3
2 5
2
3 1
5 3
2 2
*/

Compilation message (stderr)

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

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