Submission #815948

#	Time	Username	Problem	Language	Result	Execution time	Memory
815948		andecaandeci	로봇 (IOI13_robots)	C++17	76 / 100	3081 ms	61820 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 = 2e5 + 5;

set<pair<int, int>> s1, s2; 

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; 
    int l = (T - 1) / (A + B) + 1, r = T;
    while (l < r) {
        int m = (l + r) / 2, id1 = 0, id2 = 0;
        s1.clear(), s2.clear();
        for (int i = 0; i < T; i++) s1.insert({W[i], i});
        for (int i = 0; i < T; i++) s2.insert({S[i], i});
        priority_queue<pair<int, int>> pq1, pq2;
        for (auto i : s1) {
            while (id1 < A and X[id1] <= i.fi) {
                for (int j = 0; j < m and !pq1.empty(); j++) {
                    int idx = pq1.top().se;
                    s1.erase({W[idx], idx});
                    s2.erase({S[idx], idx});
                    pq1.pop();
                }
                id1++;
            }
            if (id1 == A) break;
            pq1.push({S[i.se], i.se});
        }
        while (id1 < A) {
            for (int j = 0; j < m and !pq1.empty(); j++) {
                int idx = pq1.top().se;
                s1.erase({W[idx], idx});
                s2.erase({S[idx], idx});
                pq1.pop();
            }
            id1++;
        }
        for (auto i : s2) {
            while (id2 < B and Y[id2] <= i.fi) {
                for (int j = 0; j < m and !pq2.empty(); j++) {
                    int idx = pq2.top().se;
                    s1.erase({W[idx], idx});
                    s2.erase({S[idx], idx});
                    pq2.pop();
                }
                id2++;
            }
            if (id2 == B) break;
            pq2.push({W[i.se], i.se});
        }
        while (id2 < B) {
            for (int j = 0; j < m and !pq2.empty(); j++) {
                int idx = pq2.top().se;
                s1.erase({W[idx], idx});
                s2.erase({S[idx], idx});
                pq2.pop();
            }
            id2++;
        }
        if (s1.empty()) 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;
}

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