Submission #104853

#	Time	Username	Problem	Language	Result	Execution time	Memory
104853		CorneliuVadimTudor	로봇 (IOI13_robots)	C++14	14 / 100	3085 ms	13272 KiB

robots

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

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

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({pos, V[pos].second}), pos++;
        while(pq.size() > (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 || V[Z[pos]].second >= Y[i + 1]))
            pos++;
        if(pos > (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;
}

/*
#define MAXA 50000
#define MAXB 50000
#define MAXT 1000000

int main(){
    FILE*fi,*fo;
    fi = fopen("a.in","r");
    fo = fopen("a.out","w");

    int A, B, T;
    fscanf(fi,"%d%d%d", &A, &B, &T);
    int X[MAXA], Y[MAXB], W[MAXT], S[MAXT];
    for(int i = 0; i < A; i++) fscanf(fi,"%d", &X[i]);
    for(int i = 0; i < B; i++) fscanf(fi,"%d", &Y[i]);
    for(int i = 0; i < T; i++) fscanf(fi,"%d%d", &W[i], &S[i]);

    fprintf(fo,"%d", putaway(A, B, T, X, Y, W, S));

    return 0;
}*/

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() > (i + 1) * lim){
               ~~~~~~~~~~^~~~~~~~~~~~~~~
robots.cpp:31:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(pos < Z.size() && (i == B - 1 || V[Z[pos]].second >= Y[i + 1]))
               ~~~~^~~~~~~~~~

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