Submission #1310440

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310440		am_aadvik	Robots (IOI13_robots)	C++20	76 / 100	3093 ms	32892 KiB

robots

#ifndef __ROBOTS_H__
#define __ROBOTS_H__

#ifdef __cplusplus
extern "C" {
#endif

    int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]);

#ifdef __cplusplus
}
#endif

#endif /* __ROBOTS_H__ */

#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
const int inf = 2e9+5;
#define SUBMIT 1
using namespace std;

///////////////////////////////////////////////////////////////////////////
//main code starts

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    vector<int> x(A), y(B), w(T), sz(T);
    vector<pair<int, int>> swa(T), ssa(T);
    for (int i = 0; i < A; ++i) x[i] = X[i];
    for (int i = 0; i < B; ++i) y[i] = Y[i];
    for (int i = 0; i < T; ++i) w[i] = W[i], sz[i] = S[i];
    for (int i = 0; i < T; ++i) swa[i] = { w[i], sz[i] }, ssa[i] = { sz[i], w[i] };
    sort(x.begin(), x.end()); sort(y.begin(), y.end());
    sort(swa.begin(), swa.end()); sort(ssa.begin(), ssa.end());
    x.push_back(inf);

    int s = 1, e = T, ans = -1;
    while (s <= e) {
        int t = (s + e) / 2;
        multiset<pair<int, int>> cur;
        int j = 0;
        for (int i = 0; i <= A; ++i) {
            while ((j < T) && (swa[j].first < x[i]))
                cur.insert({ swa[j].second, swa[j].first }), ++j;
            if (x[i] == inf) continue;
            if (cur.empty()) continue;
            auto it = prev(cur.end()); int op = t;
            while ((op--) && !cur.empty()){
                if (it != cur.begin())
                    --it,
                    cur.erase(next(it));
                else {
                    cur.erase(it);
                    break;
                }
            }
        }
        if (cur.size()) {
            auto it = prev(cur.end());
            for (int i = B - 1; i >= 0; --i) {
                if (cur.empty()) continue;
                auto it = prev(cur.end()); int op = t;
                while ((op--) && !cur.empty()) {
                    if ((*it).first >= y[i]) break;
                    if (it != cur.begin())
                        --it,
                        cur.erase(next(it));
                    else {
                        cur.erase(it);
                        break;
                    }
                }
            }
        }
        bool ok = cur.empty();
        if (ok) ans = t, e = t - 1;
        else s = t + 1;
    }
    return ans;
}
///////////////////////////////////////////////////////////////////////////

#ifndef SUBMIT
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int a, b, t; cin >> a >> b >> t;
    int x[1000], y[1000], w[1000], s[1000];
    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);
}
#endif

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