Submission #1009284

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009284		c2zi6	Robots (IOI13_robots)	C++14	100 / 100	2117 ms	40060 KiB

robots

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#include "robots.h"

namespace TEST3 {
    struct TOY {
        int w, s, i;
    };
    struct comp {
        bool operator()(const TOY& a, const TOY& b) {
            return a.s < b.s;
        }
    };
    int solve(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
        VI a(A);
        rep(i, A) a[i] = X[i];
        sort(all(a));
        VI b(B);
        rep(i, B) b[i] = Y[i];
        sort(all(b));
        vector<TOY> ws(T);
        rep(i, T) ws[i] = {W[i], S[i], i};
        auto can = [&](int s){
            VI taken(T);
            vector<TOY> avbl = ws;
            sort(all(avbl), [](const TOY& a, const TOY& b){return a.w > b.w;});
            priority_queue<TOY, vector<TOY>, comp> handle;
            for (int x : a) {
                while (avbl.size() && avbl.back().w < x) {
                    handle.push(avbl.back());
                    avbl.pop_back();
                }
                int c = 0;
                while (handle.size() && c < s) {
                    taken[handle.top().i] = true;
                    handle.pop();
                    c++;
                }
            }
            avbl.clear();
            for (TOY& t : ws) if (!taken[t.i]) avbl.pb(t);
            sort(all(avbl), [](const TOY& a, const TOY& b){return a.s > b.s;});
            for (int x : b) {
                vector<TOY> handle;
                while (avbl.size() && avbl.back().s < x && handle.size() < s) {
                    handle.pb(avbl.back());
                    avbl.pop_back();
                }
                for (auto&[w, s, i] : handle) taken[i] = true;
            }
            for (int x : taken) if (!x) return false;
            return true;
        };
        int l = 0;
        int r = T+1;
        while (l + 1 < r) {
            int m = (l + r) / 2;
            if (can(m)) r = m;
            else l = m;
        }
        if (r == T+1) return -1;
        return r;
    }
};

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    return TEST3::solve(A, B, T, X, Y, W, S);
}

Compilation message (stderr)

robots.cpp: In lambda function:
robots.cpp:74:74: warning: comparison of integer expressions of different signedness: 'std::vector<TEST3::TOY>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   74 |                 while (avbl.size() && avbl.back().s < x && handle.size() < s) {
      |                                                            ~~~~~~~~~~~~~~^~~
robots.cpp:78:27: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   78 |                 for (auto&[w, s, i] : handle) taken[i] = true;
      |                           ^

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