Submission #852707

#	Time	Username	Problem	Language	Result	Execution time	Memory
852707		anha3k25cvp	Robots (IOI13_robots)	C++14	100 / 100	1333 ms	25164 KiB

robots

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define dl double
#define st first
#define nd second
#define II pair <int, int>
#include "robots.h"

using namespace std;

int a, b, t;
vector <int> x, y, posx, posy;
vector <II> e;

int check(int lim) {
    priority_queue <int> q;
    int pos = 0;
    for (int i = 1; i <= a; i ++) {
        while (pos < t && e[pos].st < x[i]) {
            q.push(e[pos].nd);
            pos ++;
        }
        for (int cnt = 0; cnt < lim; cnt ++) {
            if (q.empty())
                break;
            q.pop();
        }
    }
    while (pos < t) {
        q.push(e[pos].nd);
        pos ++;
    }
    for (int i = b; i > 0; i --)
        for (int cnt = 0; cnt < lim; cnt ++) {
            if (q.empty())
                break;
            if (q.top() < y[i])
                q.pop();
            else
                return 0;
        }
    return q.empty();
}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    a = A; b = B; t = T;
    x.assign(a + 1, 0);
    for (int i = 1; i <= a; i ++)
        x[i] = X[i - 1];
    y.assign(b + 1, 0);
    for (int i = 1; i <= b; i ++)
        y[i] = Y[i - 1];
    for (int i = 0; i < T; i ++)
        e.push_back({W[i], S[i]});
    sort(x.begin() + 1, x.end());
    sort(y.begin() + 1, y.end());
    sort(e.begin(), e.end());
    int lo = 1, hi = t + 1;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (check(mid))
            hi = mid;
        else
            lo = mid + 1;
    }
    if (lo == t + 1)
        lo = -1;
    return lo;
}

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