Submission #889445

#	Time	Username	Problem	Language	Result	Execution time	Memory
889445		dwuy	Robots (IOI13_robots)	C++14	0 / 100	2 ms	12636 KiB

robots

/// dwuy: _,\,,,_\,__,\,,_
#include "robots.h"
#include <bits/stdc++.h>

#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout)
#define fi first
#define se second
#define endl "\n"
#define len(s) int32_t(s.length())
#define MASK(k)(1LL<<(k))
#define TASK "test"

using namespace std;

typedef tuple<int, int, int> tpiii;
typedef pair<double, double> pdd;
typedef pair<int, int> pii;
typedef long long ll;

const long long OO = 1e18;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int MX = 1000005;

int n, m, t;
int cnt[MX];
int weak[MX];
int small[MX];
pii a[MX];
pii b[MX];

bool ok(int mid){
    priority_queue<pair<int, int>> Q;
    set<pair<int, int>> st;
    for(int i=1; i<=m; i++) cnt[i] = mid, st.insert({small[i], i});
    bitset<MX> vist = 0;
    for(int i=t; i>=1; i--){
        auto itr = st.lower_bound({a[i].se+1, -1});
        if(itr == st.end()) continue;
        if(--cnt[itr->se] == 0) st.erase(itr);
        vist[i] = 1;
    }
    for(int i=1, j=1, cur=0; i<=t; i++){
        if(j>m) break;
        if(!vist[i]){
            if(a[i].fi > weak[j]) continue;
            if(++cur==mid) j++, cur=0;
            vist[i] = 1;
        }
    }
    for(int i=1; i<=t; i++) if(!vist[i]) return 0;
    return 1;
}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]){
    tie(n, m, t) = {A, B, T};
    for(int i=0; i<n; i++) weak[i+1] = X[i];
    for(int i=0; i<m; i++) small[i+1] = Y[i];
    for(int i=0; i<t; i++) a[i+1] = {W[i], S[i]};
    sort(weak+1, weak+1+n, greater<int>());
    sort(small+1, small+1+m, greater<int>());
    sort(a+1, a+1+t);
    int ans = -1;
    for(int lo=1, hi=t; lo<=hi;){
        int mid = (lo+hi)>>1;
        if(ok(mid)) ans = mid, hi = mid - 1;
        else lo = mid + 1;
    }
    return ans;
}

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