Submission #639243

#	Time	Username	Problem	Language	Result	Execution time	Memory
639243		classic	Robots (IOI13_robots)	C++14	100 / 100	1579 ms	24420 KiB

robots

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

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<pair<int, int>> c;
    for (int i = 0; i < t; i++) {
        c.emplace_back(w[i], s[i]);
    }
    sort(c.begin(), c.end());
    int low = 1, hig = t;
    int res = -1;
    while (low <= hig) {
        int mid = (low + hig) >> 1;
        priority_queue<int> pq;
        int idx = 0;
        for (int i = 0; i < a; i++) {
            while (idx < t && c[idx].first < x[i]) {
                pq.emplace(c[idx].second);
                idx += 1;
            }
            int cnt = 0;
            while (!pq.empty() && cnt < mid) {
                pq.pop();
                cnt += 1;
            }
        }
        while (idx < t) {
            pq.emplace(c[idx].second);
            idx += 1;
        }
        bool ok = true;
        for (int i = b - 1; i >= 0; i--) {
            int cnt = 0;
            while (!pq.empty() && cnt < mid) {
                if (pq.top() >= y[i]) {
                    ok = false;
                }
                pq.pop();
                cnt += 1;
            }
        }
        ok &= pq.empty();
        if (ok) {
            res = mid;
            hig = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return res;
}

//const int N = 1e6 + 1;
//
//int x_[N], y_[N], w_[N], s_[N];
//
//int main() {
//    ios::sync_with_stdio(false);
//    cin.tie(0);
//    int a, b, t;
//    cin >> a >> b >> t;
//    for (int i = 0; i < a; i++) {
//        cin >> x_[i];
//    }
//    for (int i = 0; i < b; i++) {
//        cin >> y_[i];
//    }
//    for (int i = 0; i < t; i++) {
//        cin >> w_[i] >> s_[i];
//    }
//    cout << putaway(a, b, t, x_, y_, w_, s_);
//    return 0;
//}

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