제출 #1324359

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1324359		sh_qaxxorov_571	로봇 (IOI13_robots)	C++20	100 / 100	1224 ms	12616 KiB

robots

#include "robots.h"
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

struct Toy {
    int w, s;
};

bool compareToys(const Toy& a, const Toy& b) {
    return a.w < b.w;
}

bool check(int M, int A, int B, int T, int X[], int Y[], vector<Toy>& toys) {
    priority_queue<int> pq;
    int j = 0;

    // Kuchsiz robotlar o'z ishini qiladi
    for (int i = 0; i < A; i++) {
        // Robot X[i] ko'tara oladigan barcha o'yinchoqlarni navbatga qo'shamiz
        while (j < T && toys[j].w < X[i]) {
            pq.push(toys[j].s);
            j++;
        }
        // Robot M ta o'yinchoqni olib ketadi (eng katta o'lchamli o'yinchoqlarni)
        int count = M;
        while (count > 0 && !pq.empty()) {
            pq.pop();
            count--;
        }
    }

    // Qolgan o'yinchoqlarni navbatga qo'shamiz
    while (j < T) {
        pq.push(toys[j].s);
        j++;
    }

    // Kichik robotlar qolgan o'yinchoqlarni oladi
    for (int i = B - 1; i >= 0; i--) {
        int count = M;
        while (count > 0 && !pq.empty()) {
            if (pq.top() < Y[i]) {
                pq.pop();
                count--;
            } else {
                // Agar eng katta o'lchamli o'yinchoqni bu robot ololmasa, 
                // demak kichikroq robotlar ham ololmaydi
                break;
            }
        }
    }

    return pq.empty();
}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    // Robotlarni saralash
    sort(X, X + A);
    sort(Y, Y + B);

    vector<Toy> toys(T);
    for (int i = 0; i < T; i++) {
        toys[i] = {W[i], S[i]};
    }
    sort(toys.begin(), toys.end(), compareToys);

    // Imkonsizlikni tekshirish
    for (int i = 0; i < T; i++) {
        bool can_be_picked = false;
        if (A > 0 && toys[i].w < X[A - 1]) can_be_picked = true;
        if (B > 0 && toys[i].s < Y[B - 1]) can_be_picked = true;
        if (!can_be_picked) return -1;
    }

    // Binary Search
    int low = 1, high = T, ans = T;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (check(mid, A, B, T, X, Y, toys)) {
            ans = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    return ans;
}

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