Submission #1026432

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026432		onbert	Robots (IOI13_robots)	C++17	100 / 100	2095 ms	59984 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
struct toy {
    int w, s, id;
    bool operator < (const toy &b) const {
        if (w!=b.w) return w < b.w;
        if (s!=b.s) return s < b.s;
        return id < b.id;
    }
};
struct thing {
    int w, s, id;
    bool operator < (const thing &b) const {
        return s < b.s;
    }
};
int32_t putaway(int32_t n, int32_t m, int32_t k, int32_t x[], int32_t y[], int32_t W[], int32_t S[]) {
    sort(x, x+n);
    sort(y, y+m);
    int mxw = 0, mxs = 0;
    if (n > 0) mxw = x[n-1];
    if (m > 0) mxs = y[m-1];
    toy a[2][k];
    for (int i=0;i<k;i++) {
        a[0][i] = {W[i], S[i], -1};
        a[1][i] = {S[i], W[i], -1};
        if (W[i] >= mxw && S[i] >= mxs) return -1;
    }
    sort(a[0], a[0]+k); sort(a[1], a[1]+k);
    for (int i=0;i<k;i++) a[1][i].id = i;
    set<toy> s;
    for (int i=0;i<k;i++) s.insert(a[1][i]);
    for (int i=0;i<k;i++) {
        toy bnd = {a[0][i].s, a[0][i].w, -1};
        toy cur = *s.lower_bound(bnd);
        a[0][i].id = cur.id;
        s.erase(cur);
    }

    int32_t l = 1, r = k;
    while (l<r) {
        int each = (l+r)/2;
        bool used[k];
        for (int i=0;i<k;i++) used[i] = false;
        priority_queue<thing> pq;
        int pt = -1;
        for (int i=0;i<n;i++) {
            int lim = x[i];
            while (pt<k-1 && a[0][pt+1].w < lim) {
                pt++;
                pq.push({a[0][pt].w, a[0][pt].s, a[0][pt].id});
                // cout << "add " << lim << " " << a[0][pt].w << " " << a[0][pt].s << endl;
            }
            for (int j=0;j<each;j++) {
                if (pq.size()==0) break;
                thing cur = pq.top();
                used[cur.id] = true;
                // cout << lim << " " << cur.w << " " << cur.s << endl;
                pq.pop();
            }
        }
        pt = -1;
        for (int i=0;i<m;i++) {
            int lim = y[i];
            int cnt = 0;
            while (cnt<each && pt<k-1 && a[1][pt+1].w<lim) {
                pt++;
                if (!used[pt]) cnt++;
                used[pt] = true;
            }
        }
        bool ok = true;
        for (int i=0;i<k;i++) if (!used[i]) ok = false;
        if (ok) r = each;
        else l = each + 1;
    }
    return l;
}

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