Submission #1141900

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141900		Sang	Robots (IOI13_robots)	C++20	100 / 100	1231 ms	24996 KiB

robots

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

#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; i--)
#define fi first
#define se second
#define pb push_back
#define ALL(a) (a).begin(), (a).end()
#define task "kbsiudthw"

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef pair<int, ii> pii;

const int N = 1e6 + 5;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 2277;

pii w[N], s[N];
bool marked[N];

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]){
    if (A)
        sort(X, X + A);
    if (B)
        sort(Y, Y + B);
    FOR (i, 0, T - 1) w[i] = {W[i], {S[i], i}}, s[i] = {S[i], {W[i], i}};
    sort(w, w + T);
    sort(s, s + T);
    int l = 1, r = T, ans = -1;
    while (l <= r){
        int m = (l + r)/2;
        FOR (i, 0, T - 1) marked[i] = 0;
        priority_queue<ii> Q;
        int ix = 0;
        int cnt = 0;
        FOR (i, 0, A - 1){
            while (ix < T && w[ix].fi < X[i]){
                Q.push(w[ix].se);
                ix++;
            }
            FOR (j, 1, m){
                if (Q.empty()) break;
                marked[Q.top().se] = 1;
                Q.pop();
            }
        }
        int iy = 0;
        FOR (i, 0, B - 1){
            while (iy < T && (marked[s[iy].se.se] || s[iy].fi < Y[i])){
                cnt += marked[s[iy].se.se] == 0;
                marked[s[iy].se.se] = 1;
                iy++;
            }
            cnt = max(0, cnt - m);
        }
        while (iy < T && marked[s[iy].se.se]) ++iy;
        if (iy == T && cnt == 0){
            ans = m;
            r = m - 1;
        } else l = m + 1;
    }
    return ans;

}

//signed main(){
//    ios_base::sync_with_stdio(0);
//    cin.tie(0); cout.tie(0);
//    if (fopen(task".inp", "r")){
//        freopen(task".inp", "r", stdin);
//        freopen(task".out", "w", stdout);
//    }
//    int X[] = {6, 2, 9};
//    int Y[] = {4, 7};
//    int W[] = {4, 8, 2, 7, 1, 5, 3, 8, 7, 10};
//    int S[] = {6, 5, 3, 9, 8, 1, 3, 7, 6, 5};
//    cout << putaway(3, 2, 10, X, Y, W, S) << '\n';
//
//    return 0;
//}

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