Submission #307174

#	Time	Username	Problem	Language	Result	Execution time	Memory
307174		vipghn2003	Robots (IOI13_robots)	C++14	90 / 100	3070 ms	15608 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];
vector<tuple<int,int,int>>order;

bool check(int lim)
{
    multiset<pii>curS,curW;
    for(int i=0;i<b;i++) curS.insert(mp(y[i],lim));
    for(int i=0;i<a;i++) curW.insert(mp(x[i],lim));
    for(auto&x:order)
    {
        int w=get<0>(x);
        int s=get<1>(x);
        int id=get<2>(x);
        auto it=curS.upper_bound(mp(s,1e9));
        if(it!=curS.end())
        {
            pii tmp=*it;
            curS.erase(it);
            if(tmp.se!=1) curS.insert(mp(tmp.fi,tmp.se-1));
        }
        else
        {
            auto it1=curW.upper_bound(mp(w,1e9));
            if(it1==curW.end()) return false;
            pii tmp=*it1;
            curW.erase(it1);
            if(tmp.se!=1) curW.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;
}

Compilation message (stderr)

robots.cpp: In function 'bool check(int)':
robots.cpp:22:13: warning: unused variable 'id' [-Wunused-variable]
   22 |         int id=get<2>(x);
      |             ^~

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