Submission #810880

#	Time	Username	Problem	Language	Result	Execution time	Memory
810880		Boomyday	Robots (IOI13_robots)	C++17	100 / 100	1555 ms	24416 KiB

robots

//
// Created by adavy on 8/6/2023.
//
//
// Created by adavy on 3/23/2023.
//
//
// Created by adavy on 2/12/2023.
//
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using db = double;
using str = string; // yay python!

using ii = pair<int,int>;
using pl = pair<ll,ll>;
using pd = pair<db,db>;

using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vii = vector<ii>;
using vpl = vector<pl>;
using vpd = vector<pd>;

#define tcT template<class T
#define tcTU tcT, class U

tcT> using V = vector<T>;
tcT, size_t SZ> using AR = array<T,SZ>;
tcT> using PR = pair<T,T>;

// pairs
#define mp make_pair
#define f first
#define s second

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

#define len(x) int((x).size())
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define sor(x) sort(all(x))
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define pb push_back
#define eb emplace_back
#define pf push_front

const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5;
const ll INF = 1e18; // not too close to LLONG_MAX
const ld PI = acos((ld)-1);
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1}; // for every grid problem!!
#include "robots.h"

bool doesWork(int time, int A, int B, int T, int X[], int Y[], int W[], int S[]){
    // Weak robots:  A,X,W
    // Small robots: B,Y,S

    // We will do first weak robots then small robots.
    int canLiftPointer = 0;



    // sort the robots
    sort(X,X+A);
    sort(Y,Y+B,greater<int>());

    // SORT THE TOYS... BY WEIGHT!!!
    vii toys;
    F0R(i,T){
        toys.pb({W[i],S[i]});
    }
    sort(all(toys));
    F0R(i,T){
        W[i] = toys[i].f;
        S[i] = toys[i].s;

    }

    priority_queue<int> toysRankedBySize;


    F0R(i, A){ // WEAK ROBOTS
        int weightLimit = lower_bound(W,W+T,X[i])-W;
        while (canLiftPointer < weightLimit){
            toysRankedBySize.push(S[canLiftPointer]);
            canLiftPointer++;

        }
        F0R(_, time){
            if (toysRankedBySize.empty()) break;
            toysRankedBySize.pop();
        }
    }
    while (canLiftPointer < T){
        toysRankedBySize.push(S[canLiftPointer]);
        canLiftPointer++;

    }


    // SMALL ROBOTS
    F0R(i, B){
        F0R(_, time){
            if (toysRankedBySize.empty()){
                return 1;
            }
            if (toysRankedBySize.top() >= Y[i]) {
                return 0;
            }
            toysRankedBySize.pop();
        }
    }
    if (toysRankedBySize.empty()){
        return 1;
    }
    return 0;

}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    ll lb = 0;
    ll ub = T+8;

    while (lb<ub){
        int mid = lb + (ub-lb)/2;
        if (doesWork(mid,A,B,T,X,Y,W,S)) {
            ub = mid;
        }
        else lb = mid+1;
    }
    if (ub==T+8) return -1;
    else return lb;

}

/*
#include <stdio.h>
#include <stdlib.h>


#define fail(s, x...) do { \
		fprintf(stderr, s "\n", ## x); \
		exit(1); \
	} while(0)

#define MAX_A 50000
#define MAX_B 50000
#define MAX_T 500000

static int X[MAX_A];
static int Y[MAX_B];
static int W[MAX_T];
static int S[MAX_T];

int main() {
    int A, B, T, i;
    int res;

    FILE *f = fopen("robots.in", "r");
    if (!f)
        fail("Failed to open input file.");

    res = fscanf(f, "%d", &A);
    if (res != 1)
        fail("Failed to read A from input file.");
    if (A < 0 || A > MAX_A)
        fail("A is out of bounds.");

    res = fscanf(f, "%d", &B);
    if (res != 1)
        fail("Failed to read B from input file.");
    if (B < 0 || B > MAX_B)
        fail("B is out of bounds.");

    res = fscanf(f, "%d", &T);
    if (res != 1)
        fail("Failed to read T from input file.");
    if (T < 1 || T > MAX_T)
        fail("T is out of bounds.");

    for (i = 0; i < A; i++) {
        res = fscanf(f, "%d", &X[i]);
        if (res != 1)
            fail("Failed to read data from input file.");
    }
    for (i = 0; i < B; i++) {
        res = fscanf(f, "%d", &Y[i]);
        if (res != 1)
            fail("Failed to read data from input file.");
    }
    for (i = 0; i < T; i++) {
        res = fscanf(f, "%d%d", &W[i], &S[i]);
        if (res != 2)
            fail("Failed to read data from input file.");
    }
    fclose(f);

    int answer = putaway(A, B, T, X, Y, W, S);

    printf("%d\n", answer);

    return 0;
}
*/

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