Submission #546288

#	Time	Username	Problem	Language	Result	Execution time	Memory
546288		Jomnoi	Robots (IOI13_robots)	C++17	100 / 100	1909 ms	28404 KiB

robots

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

class Toy {
public :
    int weight, size;
    Toy() {}
    Toy(const int &w, const int &s) : weight(w), size(s) {}

    bool operator<(const Toy &o) const {
        return size < o.size;
    }
};

bool compare(const Toy &a, const Toy &b) {
    return a.weight < b.weight;
}

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 <Toy> toy;
    for(int i = 0; i < T; i++) {
        if(W[i] >= X[A - 1] and S[i] >= Y[B - 1]) {
            return -1;
        }

        toy.push_back(Toy(W[i], S[i]));
    }
    sort(toy.begin(), toy.end(), compare);

    int l = 1, r = T, ans;
    while(l <= r) {
        int mid = (l + r) / 2;

        int j = 0;
        priority_queue <Toy> pq;
        for(int i = 0; i < A; i++) {
            while(j < T and toy[j].weight < X[i]) {
                pq.emplace(toy[j++]);
            }
            int cnt = mid;
            while(cnt-- and !pq.empty()) {
                pq.pop();
            }
        }

        while(j < T) {
            pq.emplace(toy[j++]);
        }
        for(int i = B - 1; i >= 0; i--) {
            int cnt = mid;
            while(cnt-- and !pq.empty() and pq.top().size < Y[i]) {
                pq.pop();
            }
        }

        if(pq.empty()) {
            ans = mid;
            r = mid - 1;
        }
        else {
            l = mid + 1;
        }
    }
    return ans;
}

Compilation message (stderr)

robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:33:23: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   33 |     int l = 1, r = T, ans;
      |                       ^~~

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