Submission #870867

#	Time	Username	Problem	Language	Result	Execution time	Memory
870867		LOLOLO	Robots (IOI13_robots)	C++17	100 / 100	1926 ms	56872 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())

const int N = 1e6 + 100;
bool used[N];
vector <vector <int>> save;

void process(int m, vector <int> &x) {
    mem(used, 0);
    int j = 0;
    priority_queue <pair <int, int>> pq;

    for (auto t : x) {
        while (j < sz(save) && save[j][0] < t) {
            pq.push({save[j][1], save[j][2]});
            j++;
        }

        for (int i = 0; i < m; i++) {
            if (pq.empty()) 
                break;

            auto t = pq.top();
            used[t.s] = 1;
            pq.pop();
        }
    }
}

bool check(int m, vector <int> &y, vector <int> &need) {
    int j = 0, cnt = 0, v = 0;
    for (auto x : y) {
        while (j < sz(need) && need[j] < x) {
            j++;
            v++;
        }

        cnt += min(m, v);
        v -= min(v, m);
    }

    return cnt == sz(need);
}

int putaway(int a, int b, int t, int _x[], int _y[], int _w[], int _s[]) {
    vector <int> x, y, w, s;
    for (int i = 0; i < t; i++) {
        w.pb(_w[i]);
        s.pb(_s[i]);
    }

    for (int i = 0; i < a; i++) {
        x.pb(_x[i]);
    }

    for (int i = 0; i < b; i++) {
        y.pb(_y[i]);
    }

    for (int i = 0; i < t; i++) {
        save.pb({w[i], s[i], i});
    }

    sort(all(x));
    sort(all(y));
    sort(all(save));

    int l = 1, r = t, m, ans = -1;

    while (l <= r) {
        m = (l + r) / 2;
        process(m, x);

        vector <int> need;
        for (int i = 0; i < t; i++) {
            if (used[i] == 0) {
                need.pb(s[i]);
            }
        }

        sort(all(need));
        if (check(m, y, need)) {
            ans = m;
            r = m - 1;
        } else {
            l = m + 1;
        }
    }

    return ans;
}

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