Submission #361337

#	Time	Username	Problem	Language	Result	Execution time	Memory
361337		bigDuck	Robots (IOI13_robots)	C++14	53 / 100	2427 ms	33368 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;

        multiset<pii> ac;
        int cr=0;
        for(int i=0; i<A; i++){
            while( (cr<pr.size()) && (pr[cr].ft<X[i]) ){
                ac.insert(pr[cr]); cr++;
            }
            for(int j=0; (j<mid)&&(ac.size()>0); j++){
                auto it=ac.end(); it--; ac.erase(it);
            }
        }

        multiset<pii> ac2;
        for(auto it=ac.begin(); it!=ac.end(); it++){
            ac2.insert({it->sc, it->ft} );
        }

        for(int i=cr; i<pr.size();i++){
            ac2.insert({pr[i].sc, pr[i].ft});
        }

        for(int i=0; i<B; i++){
            for(int j=0; (ac2.size()>0) && (j<mid) && (ac2.begin()->ft<Y[i] ); j++){
                ac2.erase(ac2.begin());
            }
        }
        if(ac2.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:32: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]
   32 |             while( (cr<pr.size()) && (pr[cr].ft<X[i]) ){
      |                     ~~^~~~~~~~~~
robots.cpp:45: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]
   45 |         for(int i=cr; i<pr.size();i++){
      |                       ~^~~~~~~~~~

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