Submission #660081

#	Time	Username	Problem	Language	Result	Execution time	Memory
660081		kith14	Robots (IOI13_robots)	C++17	100 / 100	1505 ms	24504 KiB

robots

#include<bits/stdc++.h>
#include "robots.h"
using namespace std;

#define ll int
#define db double
#define pairll pair<ll,ll>
#define lpairll pair<ll,pairll>

#define repp(i,a,b) for (int i = (a); i <= (b); i++)
#define repz(i,a,b) for (int i = (a); i < (b); i++)
#define repm(i,a,b) for (int i = (a); i >= (b); i--)
#define fr first
#define sc second
#define mp make_pair
#define pb push_back

const ll N = 5e5+5;
ll tc = 1, n, m, k;
string s, s1, s2, ye = "YES", no = "NO";
vector<pairll> toys;

bool pos(ll key, ll wei[], ll siz[]){
    priority_queue<ll> pq;
    ll idx = 0;
    repp(i,0,n-1){
        while(idx < k && toys[idx].fr < wei[i]){
            pq.push(toys[idx].sc);
            idx++;
        }
        ll quan = 0;
        while(pq.size() && quan < key){
            quan++;
            pq.pop();
        }
    }
    while(idx < k){
        pq.push(toys[idx].sc);
        idx++;
    }
    repm(i,m-1,0){
        ll quan = 0;
        while(pq.size() && quan < key && pq.top() < siz[i]){
            pq.pop();
            quan++;
        }
    }
    return pq.empty();
}

ll putaway(ll A, ll B, ll T, ll X[], ll Y[], ll W[], ll S[]){
    n = A, m = B, k = T;
    //X = weight, Y = size
    sort (X,X+A);
    sort (Y,Y+B);
    repp(i,0,T-1){
        toys.pb(mp(W[i],S[i]));
        if (W[i] >= X[n-1] && S[i] >= Y[m-1]) return -1;
    }
    sort(toys.begin(),toys.end());
    ll l = 1, r = k, ret;
    while(l <= r){
        ll md = (l+r)/2;
        if (pos(md,X,Y)){
            ret = md;
            r = md-1;
        }
        else l = md+1;
    }
    return ret;
}

// void input(){
//     cin >> n >> m >> k;
//     ll ar[n], br[m], cr[k], dr[k];
//     repp(i,0,n-1) cin >> ar[i];
//     repp(i,0,m-1) cin >> br[i];
//     repp(i,0,k-1) cin >> cr[i];
//     repp(i,0,k-1) cin >> dr[i];
//     cout << putaway(n,m,k,ar,br,cr,dr) << endl;
// }

// void solve(){
    
// }

// int main(){
//     ios_base::sync_with_stdio(0);
//     cin.tie(NULL); cout.tie(NULL);
//     //cin >> tc;
//     while(tc--){
//       input();
//       solve();
//     }
// }

Compilation message (stderr)

robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:61:22: warning: 'ret' may be used uninitialized in this function [-Wmaybe-uninitialized]
   61 |     ll l = 1, r = k, ret;
      |                      ^~~

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