Submission #1314804

#	Time	Username	Problem	Language	Result	Execution time	Memory
1314804		orgiloogii	Robots (IOI13_robots)	C++20	53 / 100	1205 ms	12444 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
int putaway(int n, int m, int t, int x[], int y[], int w[], int s[]) {
    vector <pair <int, int>> v;
    for (int i = 0;i < t;i++) {
        v.push_back({w[i], s[i]});
    }
    sort(v.begin(), v.end());
    int l = 0, r = t + 1;
    sort(y, y + m);
    sort(x, x + n);
    for (int i = 0;i < t;i++) {
        if (v[i].ss >= y[m - 1] && v[i].ff >= x[n - 1]) {
            return -1;
        }
    }
    while (l + 1 < r) {
        int tm = (l + r) / 2;

        priority_queue <int> pq;
        int k = 0;
        int i = 0;
        for (int id = 0;id < n;id++) {
            for (i = k;i < t;i++) {
                if (x[id] <= v[i].ff) {
                    break;
                }
                pq.push(v[i].ss);
            }
            k = i;
            int rem = 0;
            while (!pq.empty()) {
                if (rem == tm) break;
                rem++;
                pq.pop();
            }
        }
        while (i < t) {
            pq.push(v[i].ss);
            i++;
        }

        int j = 0;
        int cnt = 0;
        while (!pq.empty()) {
            if (cnt == tm || y[j] <= pq.top()) {
                j++;
                cnt = 0;
            }
            if (j >= m) break;
            cnt++;
            pq.pop();
        }
        //cout << tm << endl;
        if (pq.empty()) {
            r = tm;
        }
        else {
                /*
            while (!pq.empty()) {
                cout << pq.top() << " ";
                pq.pop();
            }
            cout << endl;
            */
            l = tm;
        }
    }
    if (r == t + 1) return -1;
    return r;
}

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