Submission #581903

#	Time	Username	Problem	Language	Result	Execution time	Memory
581903		tranxuanbach	Robots (IOI13_robots)	C++17	76 / 100	3079 ms	15100 KiB

robots

#ifndef FEXT

#include "robots.h"

#endif

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (auto i = l; i < r; i++)
#define ForE(i, l, r) for (auto i = l; i <= r; i++)
#define FordE(i, l, r) for (auto i = l; i >= r; i--)
#define Fora(v, a) for (auto v: a)
#define bend(a) a.begin(), a.end()
#define isz(a) ((signed)a.size())

using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pair <int, int>>;
using vvi = vector <vector <int>>;

const int N = 5e4 + 5, M = 1e6 + 5;

int n1, n2, m;
pii a[M];
int b[N], c[N];

int f[M], rf[M];
bool ck[M];

auto cmp1 = [](int i, int j){
    return a[i].se < a[j].se;
};

priority_queue <int, vi, decltype(cmp1)> pq1(cmp1);

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]){
    n1 = A; n2 = B; m = T;
    For(i, 0, n1){
        b[i] = X[i];
    }
    For(i, 0, n2){
        c[i] = Y[i];
    }
    For(i, 0, m){
        a[i] = make_pair(W[i], S[i]);
    }

    sort(a, a + m, [&](const pii &lhs, const pii &rhs){
        return lhs.fi < rhs.fi;
    });
    {
        iota(f, f + m, 0);
        sort(f, f + m, [&](int i, int j){
            return a[i].se < a[j].se;
        });
        For(i, 0, m){
            rf[f[i]] = i;
        }
    }
    sort(b, b + n1);
    sort(c, c + n2);

    int lo = 1, hi = m + 1;
    while (lo < hi){
        int mid = (lo + hi) >> 1;

        fill(ck, ck + m, 0);
        while (!pq1.empty()){
            pq1.pop();
        }

        int j = 0;
        For(i, 0, n1){
            while (j < m and a[j].fi < b[i]){
                pq1.emplace(j);
                j++;
            }
            ForE(turn, 1, mid){
                if (pq1.empty()){
                    break;
                }
                int j = pq1.top(); pq1.pop();
                ck[rf[j]] = 1;
            }
        }

       j = 0;

        For(i, 0, n2){
            ForE(turn, 1, mid){
                while (j < m and ck[j]){
                    j++;
                }
                if (j == m or a[f[j]].se >= c[i]){
                    break;
                }
                j++;
            }
        }
        
        while (j < m and ck[j]){
            j++;
        }

        if (j == m){
            hi = mid;
        }
        else{
            lo = mid + 1;
        }
    }
    if (lo == m + 1){
        lo = -1;
    }
    return lo;
}

#ifdef FEXT

#define fail(s, x...) do { \
        fprintf(stderr, s "\n", ## x); \
        exit(1); \
    } while(0)

#define MAX_A 50000
#define MAX_B 50000
#define MAX_T 500000

static int X[MAX_A];
static int Y[MAX_B];
static int W[MAX_T];
static int S[MAX_T];

signed main(){
    // ios_base::sync_with_stdio(0);
    // cin.tie(0); cout.tie(0);
    // freopen("KEK.inp", "r", stdin);
    freopen("KEK.out", "w", stdout);
    int A, B, T, i;
    int res;

    FILE *f = fopen("KEK.inp", "r");
    if (!f)
        fail("Failed to open input file.");

    res = fscanf(f, "%d", &A);
    if (res != 1)
        fail("Failed to read A from input file.");
    if (A < 0 || A > MAX_A)
        fail("A is out of bounds.");

    res = fscanf(f, "%d", &B);
    if (res != 1)
        fail("Failed to read B from input file.");
    if (B < 0 || B > MAX_B)
        fail("B is out of bounds.");

    res = fscanf(f, "%d", &T);
    if (res != 1)
        fail("Failed to read T from input file.");
    if (T < 1 || T > MAX_T)
        fail("T is out of bounds.");

    for (i = 0; i < A; i++) {
        res = fscanf(f, "%d", &X[i]);
        if (res != 1)
            fail("Failed to read data from input file.");
    }
    for (i = 0; i < B; i++) {
        res = fscanf(f, "%d", &Y[i]);
        if (res != 1)
            fail("Failed to read data from input file.");
    }
    for (i = 0; i < T; i++) {
        res = fscanf(f, "%d%d", &W[i], &S[i]);
        if (res != 2)
            fail("Failed to read data from input file.");
    }
    fclose(f);

    int answer = putaway(A, B, T, X, Y, W, S);

    printf("%d\n", answer);

    return 0;
}

#endif

/*
==================================================+
INPUT:                                            |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
OUTPUT:                                           |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
*/

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