Submission #1061924

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061924		vjudge1	Robots (IOI13_robots)	C++17	0 / 100	707 ms	46300 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());
    if(b==0)return 0;
    /*
    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;
        if(a>0){
            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++;

                }
            }
        }else{
            posible=false;
        }
        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: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 25
• Subtask 4: 0 / 37
• Subtask 5: 0 / 10