제출 #1270935

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1270935		thuhienne	로봇 (IOI13_robots)	C++20	76 / 100	3095 ms	16908 KiB

robots

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

static int A, B, T;
static int robot1[50009], robot2[50009];
static pair<int,int> toys[1000009];

// segment tree
static pair<int,int> st[4000009];

void reset(int id,int l,int r) {
    st[id] = {0,0};
    if (l == r) return;
    int mid = (l + r) >> 1;
    reset(id*2,l,mid);
    reset(id*2+1,mid+1,r);
}

void update(int id,int l,int r,int pos,int val) {
    if (l > pos || r < pos) return;
    if (l == r) {
        st[id] = {val,l};
        return;
    }
    int mid = (l + r) >> 1;
    update(id*2,l,mid,pos,val);
    update(id*2+1,mid+1,r,pos,val);
    st[id] = max(st[id*2],st[id*2 + 1]);
}

pair<int,int> get(int id,int l,int r) {
    if (l == r) return st[id];
    int mid = (l + r) >> 1;
    if (st[id*2] > st[id*2 + 1]) return get(id*2,l,mid);
    return get(id*2+1,mid+1,r);
}

bool check(int lim) {
    reset(1,1,T);
    int pt = 0;

    // Phase 1: robots yếu
    for (int i = 1; i <= A; i++) {
        while (pt < T && toys[pt + 1].first <= robot1[i]) {
            pt++;
            update(1,1,T,pt,toys[pt].second);
        }
        for (int j = 1; j <= lim; j++) {
            pair<int,int> dd = get(1,1,T);
            if (dd.first == 0) break;
            update(1,1,T,dd.second,0);
        }
    }
    while (pt < T) {
        pt++;
        update(1,1,T,pt,toys[pt].second);
    }

    // Phase 2: robots nhỏ
    priority_queue<int,vector<int>,greater<int>> leftover;
    while (true) {
        pair<int,int> dd = get(1,1,T);
        if (dd.first == 0) break;
        update(1,1,T,dd.second,0);
        leftover.push(dd.first);
    }

    for (int i = 1; i <= B; i++) {
        for (int j = 1; j <= lim; j++) {
            if (leftover.empty() || leftover.top() > robot2[i]) break;
            leftover.pop();
        }
    }
    return leftover.empty();
}

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 = 1; i <= A; i++) robot1[i] = X[i-1];
    for (int i = 1; i <= B; i++) robot2[i] = Y[i-1];
    for (int i = 1; i <= T; i++) {
        toys[i].first = W[i-1] + 1;
        toys[i].second = S[i-1] + 1;
    }

    sort(robot1 + 1, robot1 + 1 + A);
    sort(robot2 + 1, robot2 + 1 + B);
    sort(toys + 1, toys + 1 + T);

    int l = 1, r = T, ans = -1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (check(mid)) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return ans;
}

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