Submission #1233645

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233645		CodeLakVN	Robots (IOI13_robots)	C++20	14 / 100	1313 ms	16660 KiB

robots

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

#define task "main"
#define no "NO"
#define yes "YES"
#define F first
#define S second
#define vec vector
#define _mp make_pair
#define ii pair<int, int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define evoid(val) return void(std::cout << val)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)

const int MAX_T = (int)1e6 + 6;
const int MAX_N = (int)5e4 + 4;

int numWeak, numSmall, numToy;
vector<ii> toys;
vector<int> weak, small;

int ans = 0;

bool check(int limit) {
    priority_queue<ii> pq;
    int iToy = 0;
    FOR(i, 0, numWeak - 1) {
        while (iToy < numToy && toys[iToy].F < weak[i]) pq.push({toys[iToy].S, toys[iToy].F}), iToy++;
        int cnt = limit;
        while (cnt > 0 && !pq.empty()) pq.pop(), cnt--;
    }
    for (; iToy < numToy; iToy++) pq.push({toys[iToy].S, toys[iToy].F});
    FOD(i, numSmall - 1, 0) {
        int cnt = limit;
        while (cnt > 0 && !pq.empty()) pq.pop(), cnt--;
    }
    return (pq.empty());
}

int bs(int l, int r) {
    int res = -1;
    
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (check(mid)) r = (res = mid) - 1;
        else l = mid + 1;
    }
    
    return res;
}

int calc() {
    sort(weak.begin(), weak.end());
    sort(small.begin(), small.end());
    FOR(i, 0, numToy - 1) {
        if (upper_bound(weak.begin(), weak.end(), toys[i].F) != weak.end()) continue;
        if (upper_bound(small.begin(), small.end(), toys[i].S) == small.end()) return -1;
    }

    sort(toys.begin(), toys.end());

    return bs(1, numToy);
}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    numWeak = A, numSmall = B, numToy = T;
    weak.resize(numWeak);
    small.resize(numSmall);
    toys.resize(numToy);
    FOR(i, 0, numWeak - 1) weak[i] = X[i];
    FOR(i, 0, numSmall - 1) small[i] = Y[i];
    FOR(i, 0, numToy - 1) toys[i] = {W[i], S[i]};
    
    return calc();
}

/* Lak lu theo dieu nhac!!!! */

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