Submission #1336606

#	Time	Username	Problem	Language	Result	Execution time	Memory
1336606		iamhereforfun	Robots (IOI13_robots)	C++20	100 / 100	2016 ms	15000 KiB

robots

// Starcraft 2 enjoyer //

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

// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")

using namespace std;

#define LSOne(X) ((X) & -(X))

const int N = 2e5 + 5;
const int M = 1e6 + 5;
const int K = 1e3 + 5;
const int LG = 20;
const int INF = 1e18 + 5;
const int B = 1000;
const int MOD = 1e9 + 7;

int putaway(int n, int m, int q, int A[], int B[], int W[], int S[])
{
    vector<int> a, b;
    for (int x = 0; x < n; x++)
        a.push_back(A[x]);
    for (int x = 0; x < m; x++)
        b.push_back(B[x]);
    for (int &i : a)
        i--;
    for (int &i : b)
        i--;
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    vector<pair<int, int>> query;
    for (int x = 0; x < q; x++)
    {
        query.push_back({W[x], S[x]});
    }
    sort(query.begin(), query.end());
    int l = 1, r = q, ans = -1;
    // int l = 3, r = 3, ans = -1;
    while (l <= r)
    {
        int md = (l + r) / 2;
        int i = 0;
        priority_queue<int> pq;
        for (int x = 0; x < n; x++)
        {
            while (i < q)
            {
                if (query[i].first > a[x])
                {
                    break;
                }
                else
                {
                    pq.push(query[i].second);
                    i++;
                }
            }
            for (int y = 0; y < md; y++)
            {
                if (!pq.empty())
                    pq.pop();
                else
                    break;
            }
        }
        while (i < q)
        {
            pq.push(query[i].second);
            i++;
        }
        priority_queue<int> pq2;
        while (!pq.empty())
        {
            pq2.push(-pq.top());
            pq.pop();
        }
        for (int x = 0; x < m; x++)
        {
            for (int y = 0; y < md; y++)
            {
                if (pq2.empty())
                    break;
                if (-pq2.top() <= b[x])
                {
                    pq2.pop();
                }
                else
                {
                    break;
                }
            }
        }
        if (pq2.empty())
        {
            ans = md;
            r = md - 1;
        }
        else
        {
            l = md + 1;
        }
    }
    return ans;
}

Compilation message (stderr)

robots.cpp:18:22: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   18 | const int INF = 1e18 + 5;
      |                 ~~~~~^~~

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