Submission #1061929

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061929		JuanproMINE	Robots (IOI13_robots)	C++14	76 / 100	736 ms	46868 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

const int N=1000100;
const int R=100000;
int a,b,t;
vector<int>x;
vector<int>y;
vector<int>w;
vector<int>s;
vector<pair<int,int>> WS;

int itpass(int md, vector<int> tosmall){
    sort(y.rbegin(),y.rend());

    /*
    for(int i=0;i<tosmall.size();i++){
        cout<<tosmall[i]<<" ";
    }
    cout<<" TOSMALL"<<endl;
    */

    int pos=0;
    int cont=md;
    for(int i=0;i<tosmall.size();i++){
        if(pos>=b){

            return 0;
        }
        if(tosmall[i]>=y[pos]){
            //cout<<y[pos]<<" POS"<<endl;
            return 0;
        }
        cont--;
        if(cont==0){
            pos++;
            cont=md;
        }
    }
    return 1;

}

int binary(int mn, int md, int mx){


   while(mx!=md){
        priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>>pq;
        vector<int>tosmall;
        //cout<<mn<<" "<<md<<" "<<mx<<endl;
        int pos=0;
        int cont=md;
        bool posible=true;

        for(int i=0;i<t;i++){
            //cout<<WS[i].first<<" "<<x[pos]<<" WI XPOS"<<endl;
            //cout<<tosmall.size()<<endl;
            if(pos>=a){
                tosmall.pb(WS[i].second);
                posible=false;
                continue;
            }
            pq.push({WS[i].second,WS[i].first});
            if(pq.top()[1]>=x[pos]){
                tosmall.pb(pq.top()[0]);
                pq.pop();
                posible=false;
                continue;
            }

            cont--;

            if(cont==0){
                cont=md;
                pos++;

            }
        }
        
        if(posible==true){

            mx=md;
            md=(mn+mx)/2;
        }else{
            sort(tosmall.rbegin(),tosmall.rend());
            int look=itpass(md,tosmall);
            if(look==1){
                mx=md;
                md=(mn+mx)/2;

            }else{
                mn=md;
                md=(mn+mx+1)/2;

            }
        }
   }
    return mx;
}
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<t;i++){
        w.pb(W[i]);
        s.pb(S[i]);
        WS.pb({w[i],s[i]});
    }

    for(int i=0;i<a;i++){
        x.pb(X[i]);
    }
    for(int i=0;i<b;i++){
        y.pb(Y[i]);
    }
    sort(WS.rbegin(),WS.rend());
    sort(x.rbegin(),x.rend());

    int answer=binary(1,(t+3)/2,t+2);
    if(answer>t) return -1;
    return answer;

}

Compilation message (stderr)

robots.cpp: In function 'int itpass(int, std::vector<int>)':
robots.cpp:28:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for(int i=0;i<tosmall.size();i++){
      |                 ~^~~~~~~~~~~~~~~

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