Submission #241649

#	Time	Username	Problem	Language	Result	Execution time	Memory
241649		abacaba	Robots (IOI13_robots)	C++14	100 / 100	2753 ms	23928 KiB

robots

#include <iostream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include "robots.h"
#include <chrono>
#include <vector>
#include <map>
#include <random>
#include <set>
#include <algorithm>
#include <math.h>
#include <cstdio>
#include <stdio.h>
#include <queue>
#include <bitset>
#include <cstdlib>
#include <deque>
#include <cassert>
#include <stack>
using namespace std;
 
#define mp make_pair
#define f first
#define se second
#define pb push_back
#define ppb pop_back
#define emb emplace_back
#define ll long long
#define ull unsigned long long
#define cntbit(x) __builtin_popcount(x)
#define endl '\n'
#define uset unordered_set
#define umap unordered_map
#define pii pair<int, int>
#define ld long double
#define pll pair<long long, long long>
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
template <typename T> inline T range(T l, T r) {
    return uniform_int_distribution<T>(l, r)(rng);
}
 
inline void setin(string s) {
    freopen(s.c_str(), "r", stdin);
}
 
inline void setout(string s) {
    freopen(s.c_str(), "w", stdout);
}
 
template <typename T> void Min(T &a, T b) {
    a = min(a, b);
}
 
template <typename T> void Max(T &a, T b) {
    a = max(a, b);
}
 
const int inf = 2e9;
const int mod = 998244353;
const int N = 1e6 + 15;
 
int a[N], b[N];
pii s[N];
int n, m, t;
bool used[N];
int cnt[2][N];
 
set <pii> is;
 
inline bool check(int mid) {
    is.clear();
    for(int i = 1; i <= n; ++i) {
        cnt[0][i] = mid;
        is.insert({a[i], i});
    }
    for(int i = 1; i <= m; ++i)
        cnt[1][i] = mid;
    for(int i = 1; i <= t; ++i) {
        used[i] = false;
 
        set <pii>::iterator it = is.upper_bound({s[i].se, inf});
        if(it == is.end())
            continue;
 
        used[i] = true;
        if(--cnt[0][it->se] == 0)
            is.erase(it);
    }
    for(int i = 1, j = 1; i <= t; ++i) {
        if(!used[i]) {
            if(cnt[1][j] == 0)
                ++j;
            if(j > m || b[j] <= s[i].f)
                return false;
            cnt[1][j]--;
            used[i] = true;
        }
    }
    return true;
}
 
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    n = A, m = B, t = T;
    for(int i = 0; i < n; ++i)
        a[i + 1] = X[i];
    for(int i = 0; i < m; ++i)
        b[i + 1] = Y[i];
    sort(a + 1, a + 1 + n, [&](int a, int b) {
        return a > b;
    });
    sort(b + 1, b + 1 + m, [&](int a, int b) {
        return a > b;
    });
    for(int i = 0; i < t; ++i)
        s[i + 1] = {S[i], W[i]};
    sort(s + 1, s + 1 + t, [&](pii a, pii b) {
        return a > b;
    });
    int l = 1, r = t, res = -1;
    while(l <= r) {
        int mid = l + r >> 1;
        if(check(mid))
            r = mid - 1, res = mid;
        else
            l = mid + 1;
    }
    return res;
}

Compilation message (stderr)

robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:125:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = l + r >> 1;
                   ~~^~~

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