Submission #104859

#	Time	Username	Problem	Language	Result	Execution time	Memory
104859		CorneliuVadimTudor	Robots (IOI13_robots)	C++14	100 / 100	2331 ms	13668 KiB

robots

#include <bits/stdc++.h>
#include "robots.h"

struct Elem{
    int val;
    bool operator < (const Elem &aux) const{
        return val > aux.val;
    }
};

std::vector <int> Z;
std::priority_queue <Elem> pq;
int f(int lim, int A, int B, int T, int X[], int Y[], std::pair <int, int> V[]){
    Z.clear();
    while(!pq.empty()) pq.pop();

    int pos = 0;
    for(int i = -1; i < A; i++){
        while(pos < T && (i == A - 1 || V[pos].first >= X[i + 1]))
              pq.push({V[pos++].second});
        while(pq.size() > 1LL * (i + 1) * lim){
            Z.push_back(pq.top().val);
            pq.pop();
        }
    }

    std::sort(Z.begin(), Z.end());
    std::reverse(Z.begin(), Z.end());
    pos = 0;
    for(int i = -1; i < B; i++){
        while(pos < Z.size() && (i == B - 1 || Z[pos] >= Y[i + 1]))
            pos++;
        if(pos > 1LL * (i + 1) * lim) return 0;
    }

    return 1;
}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]){
    std::sort(X, X + A), std::reverse(X, X + A);
    std::sort(Y, Y + B), std::reverse(Y, Y + B);
    std::pair <int, int> V[T];

    for(int i = 0; i < T; i++)
        V[i] = {W[i], S[i]};
    std::sort(V, V + T);
    std::reverse(V, V + T);

    if(!f(T, A, B, T, X, Y, V)) return -1;
    int l = 1, r = T;
    while(r - l > 1){
        int m = (l + r) / 2;
        if(f(m, A, B, T, X, Y, V)) r = m;
        else l = m + 1;
    }
    if(f(l, A, B, T, X, Y, V)) return l;
    return r;
}

Compilation message (stderr)

robots.cpp: In function 'int f(int, int, int, int, int*, int*, std::pair<int, int>*)':
robots.cpp:21:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(pq.size() > 1LL * (i + 1) * lim){
               ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
robots.cpp:31:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(pos < Z.size() && (i == B - 1 || Z[pos] >= Y[i + 1]))
               ~~~~^~~~~~~~~~

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