Submission #383966

#	Time	Username	Problem	Language	Result	Execution time	Memory
383966		ParsaAlizadeh	Robots (IOI13_robots)	C++17	100 / 100	2315 ms	26612 KiB

robots

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

typedef long long       ll;
typedef pair<ll, ll>    pll;
typedef pair<int, int>  pii;

#define all(x)          x.begin(), x.end()
#define kill(x)         return cout << x << endl, 0
#define endl            '\n'

constexpr ll pw(ll a, ll b, ll mod) {
    return (!b    ? 1 :
            b & 1 ? a * pw(a * a % mod, b / 2, mod) % mod :
                    pw(a * a % mod, b / 2, mod));
}

constexpr int N   = 1e6 + 10;

int A, B, T, *X, *Y, *W, *S, ind[N];

bool check(int k) {
    priority_queue<pii, vector<pii>, less<pii>> pq;
    int ptr = 0;
    for (int i = 0; i < A; i++) {
        while (ptr < T && W[ind[ptr]] < X[i]) {
            pq.push({S[ind[ptr]], ind[ptr]});
            ptr++;
        }
        for (int j = 0; j < k && !pq.empty(); j++)
            pq.pop();
    }
    while (ptr < T) {
        pq.push({S[ind[ptr]], ind[ptr]});
        ptr++;
    }
    vector<int> vec;
    while (!pq.empty()) {
        vec.push_back(pq.top().second);
        pq.pop();
    }
    reverse(all(vec));
    ptr = 0;
    for (int i = 0; i < B; i++) {
        for (int j = 0; j < k && ptr < vec.size() && S[vec[ptr]] < Y[i]; j++, ptr++);
    }
    return ptr == vec.size();
}

int putaway(int _A, int _B, int _T, int _X[], int _Y[], int _W[], int _S[]) {
    A = _A, B = _B, T = _T, X = _X, Y = _Y, W = _W, S = _S;

    sort(X, X + A);
    sort(Y, Y + B);

    for (int i = 0; i < T; i++) {
        if (W[i] >= X[A - 1] && S[i] >= Y[B - 1])
            return -1;
    }

    iota(ind, ind + T, 0);
    sort(ind, ind + T, [] (int i, int j) {
        return W[i] < W[j];
    });

    int L = 0, R = T;
    while (R - L > 1) {
        int mid = (L + R) >> 1;
        (check(mid) ? R : L) = mid;
    }
    return R;
}

Compilation message (stderr)

robots.cpp: In function 'bool check(int)':
robots.cpp:46:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         for (int j = 0; j < k && ptr < vec.size() && S[vec[ptr]] < Y[i]; j++, ptr++);
      |                                  ~~~~^~~~~~~~~~~~
robots.cpp:48:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     return ptr == vec.size();
      |            ~~~~^~~~~~~~~~~~~

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