Submission #815966

#	Time	Username	Problem	Language	Result	Execution time	Memory
815966		kebine	Robots (IOI13_robots)	C++17	100 / 100	1750 ms	38584 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second

const int N = 1e6 + 5;

bool vis[N];
vector<pair<int, int>> vA, vB, v1, v2;
priority_queue<pair<int, int>> pq; 

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    sort(X, X + A);
    sort(Y, Y + B);
    for (int i = 0; i < T; i++) if (W[i] >= X[A - 1] and S[i] >= Y[B - 1]) return -1; 
    for (int i = 0; i < T; i++) vA.push_back({W[i], i});
    for (int i = 0; i < T; i++) vB.push_back({S[i], i});
    sort(vA.begin(), vA.end());
    sort(vB.begin(), vB.end());
    int l = (T - 1) / (A + B) + 1, r = T;
    while (l < r) {
        int m = (l + r) / 2, id1 = 0, id2 = 0, cnt = 0;
        v1 = vA, v2 = vB;
        while (!pq.empty()) pq.pop();
        for (int i = 0; i < T; i++) vis[i] = 0;
        for (auto i : v1) {
            while (id1 < A and X[id1] <= i.fi) {
                for (int j = 0; j < m and !pq.empty(); j++) {
                    int idx = pq.top().se;
                    vis[idx] = 1;
                    cnt++;
                    pq.pop();
                }
                id1++;
            }
            if (id1 == A) break;
            pq.push({S[i.se], i.se});
        }
        while (id1 < A) {
            for (int j = 0; j < m and !pq.empty(); j++) {
                int idx = pq.top().se;
                vis[idx] = 1;
                cnt++;
                pq.pop();
            }
            id1++;
        }
        while (!pq.empty()) pq.pop();
        for (auto i : v2) {
            if (vis[i.se]) continue;
            while (id2 < B and Y[id2] <= i.fi) {
                for (int j = 0; j < m and !pq.empty(); j++) {
                    int idx = pq.top().se;
                    cnt++;
                    pq.pop();
                }
                id2++;
            }
            if (id2 == B) break;
            pq.push({W[i.se], i.se});
        }
        while (id2 < B) {
            for (int j = 0; j < m and !pq.empty(); j++) {
                int idx = pq.top().se;
                cnt++;
                pq.pop();
            }
            id2++;
        }
        if (cnt == T) r = m;
        else l = m + 1;
        // for (auto x : s1) cout << x.fi << " " << x.se << "qihdf\n";
        // for (auto x : s2) cout << x.fi << " " << x.se << "pfawl\n";
        // cout << m << " " << s1.size() << " " << s2.size() << "fwao\n";
    }
    return l;
}

Compilation message (stderr)

robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:59:25: warning: unused variable 'idx' [-Wunused-variable]
   59 |                     int idx = pq.top().se;
      |                         ^~~
robots.cpp:70:21: warning: unused variable 'idx' [-Wunused-variable]
   70 |                 int idx = pq.top().se;
      |                     ^~~

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