Submission #141567

#	Time	Username	Problem	Language	Result	Execution time	Memory
141567		ansol4328	Robots (IOI13_robots)	C++11	100 / 100	2637 ms	41332 KiB

robots

#include "robots.h"
#include<bits/stdc++.h>

using namespace std;

struct in
{
    int w, s, idx;
    in() {}
    in(int v1, int v2, int v3) : w(v1), s(v2), idx(v3) {}
};

bool cmp1(const in &lhs, const in &rhs){ return lhs.w==rhs.w ? lhs.s>rhs.s : lhs.w<rhs.w; }
bool cmp2(const in &lhs, const in &rhs){ return lhs.s==rhs.s ? lhs.w>rhs.w : lhs.s<rhs.s; }

bool operator < (in lhs, in rhs)
{
    return lhs.s<rhs.s;
}

int cx[50005], cy[50005];
bool check[1000005];
vector<in> arr1, arr2;

bool pos(int limit, int A, int B, int T, int X[], int Y[])
{
    int idx=0, tot=T;
    memset(cx,0,sizeof(cx));
    memset(cy,0,sizeof(cy));
    memset(check,false,sizeof(check));
    priority_queue<in> PQ;
    for(int i=0 ; i<A ; i++){
        while(idx<T && arr1[idx].w<=X[i]){
            PQ.push(arr1[idx]);
            idx++;
        }
        while(!PQ.empty() && cx[i]<limit){
            tot--;
            cx[i]++;
            check[PQ.top().idx]=true;
            PQ.pop();
        }
    }
    idx=0;
    for(int i=0 ; i<B ; i++){
        while(idx<T && arr2[idx].s<=Y[i] && cy[i]<limit){
            if(check[arr2[idx].idx]){
                idx++;
                continue;
            }
            cy[i]++;
            tot--;
            idx++;
        }
    }
    return tot==0;
}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[])
{
    int xval=0, yval=0;
    sort(X,X+A);
    sort(Y,Y+B);
    for(int i=0 ; i<A ; i++) X[i]--;
    for(int i=0 ; i<B ; i++) Y[i]--;
    if(A>0) xval=X[A-1];
    if(B>0) yval=Y[B-1];
    for(int i=0 ; i<T ; i++){
        arr1.emplace_back(W[i],S[i],i);
        arr2.emplace_back(W[i],S[i],i);
        if(W[i]>xval && S[i]>yval) return -1;
    }
    sort(arr1.begin(),arr1.end(),cmp1);
    sort(arr2.begin(),arr2.end(),cmp2);
    int st=1, fn=T, mid, ret;
    while(st<=fn){
        mid=(st+fn)>>1;
        if(pos(mid,A,B,T,X,Y)) fn=mid-1, ret=mid;
        else st=mid+1;
    }
    return ret;
}

Compilation message (stderr)

robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:75:26: warning: 'ret' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int st=1, fn=T, mid, ret;
                          ^~~

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