Submission #578983

#	Time	Username	Problem	Language	Result	Execution time	Memory
578983		Mazaalai	Robots (IOI13_robots)	C++17	0 / 100	178 ms	9624 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define ff first
#define ss second
#define LINE "--------------------\n"
using namespace std;
using PII = pair <int, int>;
int n, m, k, a, b;
const int N = 5e4+5;
const int M = 1e6+5;
int wLimit[N], szLimit[N];
PII toys[M];
bool removed[N];
bool solve(int lim) {
    priority_queue <int> vals;
    // cout << LINE;
    for (int i = a-1, j = n-1; i >= 0 && j >= 0; i--) {
        while(j >= 0 && toys[j].ff >= wLimit[i]) {
            vals.push(toys[j].ss);
            // cout << "SKIP: " << j << ' ' << toys[j].ff << ' ' << toys[j].ss << '\n';
            j--;
        }
        j -= lim;
    }
    for (int i = b-1; i >= 0; i--) {
        if (!vals.empty() && vals.top() >= szLimit[i]) {
            return 0;
        }
        for (int j = 0; j < lim && !vals.empty(); j++) vals.pop();
    }
    return vals.empty();
}
int putaway(int weak, int small, int _n, int _wLimit[], int _szLimit[], int _w[], int _sz[]) {
    n = _n;
    a = weak;
    b = small;
    for (int i = 0; i < weak; i++) wLimit[i] = _wLimit[i];
    for (int i = 0; i < small; i++) szLimit[i] = _szLimit[i];
    for (int i = 0; i < n; i++) toys[i] = {_w[i], _sz[i]};
    if (n > 0) sort(toys, toys+n);
    if (a > 0) sort(wLimit, wLimit+a); 
    if (b > 0) sort(szLimit, szLimit+b);
    if (n == 0) return 0;
    int l = 1, r = n, ans = 1e9;
    while (l <= r) {
        int mid = (l+r)>>1;
        if (solve(mid)) {
            r = mid-1;
            ans = mid;
        } else {
            l = mid+1;
        }
    }
    return ans == 1e9 ? -1 : ans;
}

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