Submission #104860

#	Time	Username	Problem	Language	Result	Execution time	Memory
104860		popovicirobert	Robots (IOI13_robots)	C++14	100 / 100	1719 ms	16824 KiB

robots

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

using namespace std;

struct Comp {
    int val, pos;
    bool operator <(const Comp &other) const {
        return val < other.val;
    }
};

vector <int> ordw, ords;
vector <bool> vis;

inline bool check(int res, int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    fill(vis.begin(), vis.end(), 0);
    priority_queue <Comp> pq;

    int pos = 0, ans = 0;
    for(int i = 0; i < A; i++) {
        while(pos < T && W[ordw[pos]] < X[i]) {
            pq.push({S[ordw[pos]], ordw[pos]});
            pos++;
        }
        for(int j = 1; j <= res && pq.size(); j++) {
            auto it = pq.top();
            pq.pop();
            vis[it.pos] = 1;
            ans++;
        }
    }
    pos = 0;
    int cnt = 0;
    for(int i = 0; i < B; i++) {
        while(pos < T && S[ords[pos]] < Y[i]) {
            if(vis[ords[pos]] == 0) {
                cnt++;
            }
            pos++;
        }
        for(int j = 1; j <= res && cnt > 0; j++) {
            ans++;
            cnt--;
        }
    }
    return ans == T;
}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    sort(X, X + A), sort(Y, Y + B);
    ordw.resize(T), ords.resize(T), vis.resize(T);
    iota(ordw.begin(), ordw.end(), 0), iota(ords.begin(), ords.end(), 0);
    sort(ordw.begin(), ordw.end(), [&](const int &a, const int &b) {return W[a] < W[b];});
    sort(ords.begin(), ords.end(), [&](const int &a, const int &b) {return S[a] < S[b];});
    for(int i = 0; i < T; i++) {
        if(W[i] >= X[A - 1] && S[i] >= Y[B - 1]) {
            return -1;
        }
    }

    int res = 0, step = 1;
    while(!check(res + step, A, B, T, X, Y, W, S)) {
        res += step;
        step <<= 1;
    }
    step >>= 1;
    while(step) {
        if(!check(res + step, A, B, T, X, Y, W, S)) {
            res += step;
        }
        step >>= 1;
    }
    return res + 1;

}

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