Submission #1189215

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189215		jasonic	Robots (IOI13_robots)	C++20	100 / 100	2037 ms	29932 KiB

robots

// ty gian ily

/*

using a pqueue this time (this is what i missed), we try to assign the weak robots in such a way that they take the HEAVIEST ones they can do for some count.

afterwards, we can just consider strong robots normally (backwards order).

*/

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

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

struct Toy{
    int w, s, i; // almost in the thick of it

    Toy(): w(-1), s(-1), i(-1) {};

    Toy(int a, int b, int c): w(a), s(b), i(c) {};
};

bool vis[1000005];
vector<Toy> toysW;
vector<Toy> toysS;
vector<int> wLim;
vector<int> sLim;

struct Comp{
    bool operator()(const Toy &a, const Toy &b) { // pqueue is in reverse, it should be false throughout
        return a.w == b.w ? a.s > b.s : a.w < b.w;
    }
};

bool check(int cnt, int &a, int &b, int &t) {
    priority_queue<Toy, vector<Toy>, Comp> pq;
    int left = t;
    int sz = 0;

    for(int i = 0, j = 0, rem = cnt; i < b; i++, rem = cnt) { // greedy on the small robots
        while(j < t) { 
            if(toysS[j].s < sLim[i]) { // sorted by size, just keep going until we run out
                pq.emplace(toysS[j]); 
                j++; 
                sz++;
            } else break;
        }

        while(sz && rem) {
            Toy item = pq.top(); pq.pop(); // were popping it anyways so it makes sense that we dont need to give a crap
            vis[item.i] = true;
            sz--; rem--; left--;
        }
    }

    while(!pq.empty()) pq.pop(); // bye
    sz = 0;

    for(int i = 0, j = 0, rem = cnt; i < a; i++, rem = cnt) {
        while(j < t) { 
            if(toysW[j].w < wLim[i]) { // sorted by size, just keep going until we run out
                if(!vis[toysW[j].i]) {
                    pq.emplace(toysW[j]);
                    sz++;
                }
                
                j++;
            } else break;
        }

        while(sz && rem) {
            Toy item = pq.top(); pq.pop(); // were popping it anyways so it makes sense that we dont need to give a crap
            vis[item.i] = true;
            sz--; rem--; left--;
        }
    }

    return left == 0;
}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    for(int i = 0; i < T; i++) {
        toysW.push_back(Toy(W[i], S[i], i));
        toysS.push_back(Toy(W[i], S[i], i));
    }
    for(int i = 0; i < A; i++) {
        wLim.push_back(X[i]);
    }
    for(int i = 0; i < B; i++) {
        sLim.push_back(Y[i]);
    }

    sort(toysW.begin(), toysW.end(), [](const Toy &a, const Toy &b) {
        return a.w == b.w ? a.s < b.s : a.w < b.w;
    });

    sort(toysS.begin(), toysS.end(), [](const Toy &a, const Toy &b) {
        return a.s == b.s ? a.w < b.w : a.s < b.s;
    });

    sort(wLim.begin(), wLim.end(), less<int>());
    sort(sLim.begin(), sLim.end(), less<int>());

    int l = 0, r = T+1;

    while(l + 1 < r) {
        memset(vis, 0, sizeof(vis)); // illegal, but do i care? nah
        int m = (l+r)>>1;
        if(check(m, A, B, T)) { // its valid, add to set
            r = m;
        } else l = m;
    }

    if(r == T+1) return -1;
    return r;
}

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