Submission #997402

#	Time	Username	Problem	Language	Result	Execution time	Memory
997402		phoenix	Robots (IOI13_robots)	C++17	100 / 100	810 ms	36828 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>

const int N = 100100;
const int T = 1100100;
const int INF = 1e9;

using namespace std;

class Heap {
private:
    int arr[2 * T];
    int sz;
public:
    Heap() {
        sz = 0;
        for (int i = 1; i < T; i++)
            arr[i] = INF;
    }
    void init() {
        while (sz) {
            arr[sz--] = INF;
        }
    }
    void normalize(int v) {
        for (int i = v; i > 1 && arr[i] < arr[i / 2]; i /= 2)
            std::swap(arr[i], arr[i / 2]);
    }
    void push(int x) {
        arr[++sz] = x;
        normalize(sz);
    }
    int top() {
        return arr[1];
    }
    void pop() {
        arr[1] = INF;
        int v = 1;
        while (std::min(arr[2 * v], arr[2 * v + 1]) != INF) {
            if (arr[2 * v] <= arr[2 * v + 1]) {
                std::swap(arr[2 * v], arr[v]);
                v = 2 * v;  
            } else {
                std::swap(arr[2 * v + 1], arr[v]);
                v = 2 * v + 1;
            }
        }
        std::swap(arr[v], arr[sz]);
        sz--;
        normalize(v);
    }
    int size() {
        return sz;
    }
};

int n, m, t;
int X[T], Y[T];
int W[N], S[N];

vector<int> ord;

Heap pq;

bool check(int k) {
    pq.init();

    int l = n - 1;
    vector<int> rest;

    for (int toy : ord) {
        while (l >= 0 && W[l] > X[toy]) 
            l--;
        pq.push(Y[toy]);    
        if (1ll * (n - 1 - l) * k < pq.size()) {
            rest.push_back(pq.top());
            pq.pop();
        }
    }
    // for (int c : rest) cout << c << ' ';
    // cout << '\n';
    sort(rest.rbegin(), rest.rend());
    l = m - 1;
    long long cnt = 0;
    for (int y : rest) {
        while (m >= 0 && S[l] > y) {
            cnt += k;
            l--;
        }
        cnt--;
        if (cnt < 0) {
            return 0;
        }
    }
    return 1;
} 

int putaway(int A, int B, int T, int W_inside[], int S_inside[], int X_inside[], int Y_inside[]) {
    n = A, m = B, t = T;
    for (int i = 0; i < n; i++) W[i] = W_inside[i];
    for (int i = 0; i < m; i++) S[i] = S_inside[i];
    for (int i = 0; i < t; i++) {
        X[i] = X_inside[i];
        Y[i] = Y_inside[i];
    }
    sort(W, W + n);
    sort(S, S + m);
    ord.resize(t);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int i, int j) {
        if (X[i] != X[j]) return X[i] > X[j];
        return Y[i] > Y[j];
    });
    int l = 0, r = T + 1;
    while (r - l > 1) {
        int mid = (l + r) / 2;
        if (check(mid))
            r = mid;
        else 
            l = mid;
    }
    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