Submission #361350

#	Time	Username	Problem	Language	Result	Execution time	Memory
361350		bigDuck	Robots (IOI13_robots)	C++14	100 / 100	1939 ms	12868 KiB

robots

#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount

#include "robots.h"




int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    sort(X, X+A);
    sort(Y, Y+B);
    vector<pii> pr;
    for(int i=0; i<T; i++){
        pr.pb({W[i], S[i]});
    }
    sort(pr.begin(), pr.end());
    int l=1, r=T+1, mid=(l+r)>>1ll;
    while(l<r){
        mid=(l+r)>>1ll;

        priority_queue<int> ac;
        int cr=0;
        for(int i=0; i<A; i++){

            while( (cr<pr.size()) && (pr[cr].ft<X[i]) ){
                ac.push(pr[cr].sc); cr++;
            }
            for(int j=0; (j<mid)&&(ac.size()>0); j++){
                ac.pop();
            }
        }




        while((ac.size()>0)&&( ((int)ac.top())>0) ){
            ac.push(-ac.top());
            ac.pop();
        }
        for(int i=cr; i<pr.size(); i++){
            ac.push(-pr[i].sc);
        }
        for(int i=0; i<B; i++){
            for(int j=0; (j<mid) && (ac.size()>0) && ( (-ac.top())<Y[i] ); j++ ){
                ac.pop();
            }
        }
        if(ac.size()==0){
            r=mid;
        }
        else{
            l=mid+1;
        }
        mid=(l+r)>>1ll;
    }
    if(mid>T){
        return -1;
    }
    return mid;
}

/*int a1[1000010], a2[1000010], a3[1000010], a4[1000010];
int main(){
int a, b, n;
cin>>a>>b>>n;

for(int i=0; i<a; i++){
    cin>>a1[i];
}
for(int i=0; i<b; i++){
    cin>>a2[i];
}
for(int i=0;i<n; i++){
    cin>>a3[i]>>a4[i];
}
cout<<putaway(a, b, n, a1, a2, a3, a4);
}*/

Compilation message (stderr)

robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:33:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |             while( (cr<pr.size()) && (pr[cr].ft<X[i]) ){
      |                     ~~^~~~~~~~~~
robots.cpp:48:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         for(int i=cr; i<pr.size(); i++){
      |                       ~^~~~~~~~~~

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