Submission #1189587

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189587		tapilyoca	Robots (IOI13_robots)	C++20	100 / 100	1492 ms	27544 KiB

robots

/***********************************************
* auth: tapilyoca                              *
* date: 04/15/2025 at 12:28:45                 *
* dots: https://github.com/tapilyoca/dotilyoca * 
***********************************************/

#include <bits/stdc++.h>
#include "robots.h"
using namespace std;
const long long MOD = 1e9+7;

template<typename T>
using vec = vector<T>;
using ll = long long;
using vll = vec<ll>;
using vvll = vec<vll>;
using pll = pair<ll,ll>;
using str = string;
#define pb push_back
#define dbg(x) cerr << #x << ": " << x << endl;

/***********************************************/

struct Toy { 
    int weight, size, index;
    
    Toy(int a, int b, int c) : weight(0), size(0), index(0) {
        weight = a;
        size = b;
        index = c;
    }
};

bool byWeight(const Toy&one, const Toy&two) {
    if(one.weight == two.weight) return one.size < two.size;
    return one.weight < two.weight;
}

bool bySize(const Toy&one, const Toy&two) {
    if(one.size == two.size) return one.weight < two.weight;
    return one.size < two.size;
}

vector<Toy> toysByWeight;
vector<Toy> toysBySize;
vector<int> weak;
vector<int> small;
vector<bool> vis;
int a, b, t;

bool check(int tt) {
    // returns true if possible to get t or less
    
    // first assign weak
    int assigned = 0;
    int at = 0;
    priority_queue<pair<int,int>> pq; 

    // greedy: from weakest to strongest, get everyone they can take and let them take the biggest among those
    
    for(int i = 0; i < a; i++) {
        while(at < t) {
            // cerr << "i at " << i << " " << at << endl;
            if(toysByWeight[at].weight >= weak[i]) break;
            if(vis[toysByWeight[at].index]) {
                at++;
                continue;
            }
            pq.push({toysByWeight[at].size, toysByWeight[at].index});
            at++;
        }

        int taken = 0;
        while(!pq.empty() and taken != tt) {
            int thingWeTake = pq.top().second;
            pq.pop();
            vis[thingWeTake] = 1;
            taken++;
            assigned++;
        }
        // dbg(assigned);
    }
    // cerr << "here" << endl;

    priority_queue<pair<int,int>> pq2;
    at = 0;
    for(int i = 0; i < b; i++) {
        while(at < t) {
            // cerr << "i at " << i << " " << at << endl;
            if(toysBySize[at].size >= small[i]) break;
            if(vis[toysBySize[at].index]) {
                at++;
                continue;
            }
            // dbg(0);
            pq2.push({toysBySize[at].weight, toysBySize[at].index});
            at++;
        }

        int taken = 0;
        while(!pq2.empty() and taken != tt) {
            // cerr << "hello" << endl;
            int thingWeTake = pq2.top().second;
            pq2.pop();
            vis[thingWeTake] = 1;
            taken++;
            assigned++;
        }
    }

    if(assigned == t) {
        return true;
    } return false;
}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    a = A;
    b = B;
    t = T;

    for(int i = 0; i < A; i++) weak.pb(X[i]);
    for(int i = 0; i < B; i++) small.pb(Y[i]);
    for(int i = 0; i < T; i++) {
        toysByWeight.pb(Toy(W[i],S[i],i));
        toysBySize.pb(Toy(W[i],S[i],i));
    }

    sort(weak.begin(), weak.end());
    sort(small.begin(), small.end());
    sort(toysByWeight.begin(), toysByWeight.end(), byWeight);
    sort(toysBySize.begin(), toysBySize.end(), bySize);

    // for(int i = 0; i < t; i++) {
    //     cerr << toysByWeight[i].weight << " ";
    // } cerr << endl;

    // for(int i = 0; i < t; i++) {
    //     cerr << toysBySize[i].size << " ";
    // } cerr << endl;

    int lp = 1, rp = T;
    while(lp <= rp) {
        // cerr << lp << " " << rp << endl;
        vis.assign(t,0);
        int m = (lp+rp)>>1;
        if(check(m)) {
            // possible to get m or less so neglect right half
            rp = m - 1;
        } else {
            lp = m + 1;
        }
    }
    vis.assign(t,0);

    if(check(lp)) return lp;
    else return -1;
}

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