Submission #1187953

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187953		jasonic	Robots (IOI13_robots)	C++20	0 / 100	0 ms	328 KiB

robots

/*

bro what the hell is this

binary search again?    

*/

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

#define ll long long
#define fastIO cin.tie(0); ios::sync_with_stdio(false)

vector<pair<int, int>> toys;
vector<int> weightLim;
vector<int> weightLimCnt;
vector<int> sizeLim;
vector<int> sizeLimCnt;

bool check(int cnt, int &a, int &b, int &t) {
    int weakIdx = 0;
    int end = t-1;

    if(a != 0) while(toys[end].first >= weightLim[a-1]) {
        int l = -1, r = b;
        while(l + 1 < r) {
            int m = (l+r)/2;
            if((sizeLim[m] >= toys[end].second) and (sizeLimCnt[m] < cnt)) r = m;
            else l = m;
        }
        if(r == b) return false;
        else {sizeLimCnt[r]++;}
        end--;
    }

    for(int i = 0; i <= end; i++) {
        /*
        greedily assign to someone who can carry it (size constraint)
        otherwise, give it to the max person with weight constraint
        */
        int l = -1, r = b;
        while(l + 1 < r) {
            int m = (l+r)/2;
            if((sizeLim[m] >= toys[i].second) and (sizeLimCnt[m] < cnt)) r = m;
            else l = m;
        }

        if (r == b) { // assign it to max weight

            if(a == 0) return false;

            while((weightLim[weakIdx] < toys[i].first or weightLimCnt[weakIdx] >= cnt) and weakIdx < a) weakIdx++;

            if(weakIdx < a) {
                weightLimCnt[weakIdx]++;
                if(weightLimCnt[weakIdx] >= cnt) weakIdx++;
            } else return false;

        } else {sizeLimCnt[r]++;}
    }
    return true;
}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    // long ahh signature
    for(int i = 0; i < T; i++) {
        toys.push_back({W[i], S[i]});
    }

    for(int i = 0; i < A; i++) {
        weightLim.push_back(X[i]);
    }

    for(int i = 0; i < B; i++) {
        sizeLim.push_back(Y[i]);
    }

    sort(toys.begin(), toys.end(), [&](const pair<int, int> &a, const pair<int, int> &b) {return a.first == b.first ? a.second < b.second : a.first < b.first;});
    sort(weightLim.begin(), weightLim.end(), less<int>());
    sort(sizeLim.begin(), sizeLim.end(), less<int>());

    ll l = 0, r = T+1;

    while(l + 1 < r) {
        weightLimCnt = vector(A, 0);
        sizeLimCnt = vector(B, 0);
        ll m = (l+r)>>1;

        if(check(m, A, B, T)) {
            r = m;
        } else {
            l = m;
        }
    }
    
    if(r == T+1) {
        return -1;
    } else return r;
}

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