Submission #573506

#	Time	Username	Problem	Language	Result	Execution time	Memory
573506		Theo830	Robots (IOI13_robots)	C++17	100 / 100	2008 ms	22192 KiB

robots

#include <bits/stdc++.h>
using namespace std;
typedef int ll;
const ll INF = 1e9+7;
const ll MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ll,ii>
#define ull unsigned ll
#define f(i,a,b) for(ll i = a;i < b;i++)
#define pb push_back
#define vll vector<ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
///I hope I will get uprating and don't make mistakes
///I will never stop programming
///sqrt(-1) Love C++
///Please don't hack me
///@TheofanisOrfanou Theo830
///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst)
///Stay Calm
///Look for special cases
///Beware of overflow and array bounds
///Think the problem backwards
///Training
#include "robots.h"
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]){
    sort(X,X+A);
    sort(Y,Y+B);
    vector<ii>arr;
    f(i,0,T){
        arr.pb(ii(W[i],S[i]));
    }
    sort(all(arr));
    reverse(all(arr));
    ll ans = INF;
    ll l = 1,r = T;
    while(l <= r){
        ll mid = (l+r)/2;
        bool ok = 1;
        ll pos = A-1;
        ll ex = mid;
        set<ii>em;
        ll posa = 1;
        ll exo[B] = {0};
        f(i,1,B){
            if(Y[i-1] != Y[i]){
                em.insert(ii(Y[i-1],i - 1));
                exo[i - 1] = posa * mid;
                posa = 1;
            }
            else{
                posa++;
            }
        }
        if(B){
            em.insert(ii(Y[B - 1],B-1));
            exo[B - 1] = posa * mid;
        }
        for(auto x:arr){
            auto it = em.upper_bound(ii(x.S,INF));
            if(it == em.end()){
                if(pos == -1 || X[pos] <= x.F){
                    ok = 0;
                    break;
                }
                ex--;
                if(ex == 0){
                    pos--;
                    ex = mid;
                }
            }
            else{
                ii E = (*it);
                exo[E.S]--;
                if(exo[E.S] == 0){
                    em.erase(E);
                }
            }
        }
        if(ok){
            r = mid - 1;
            ans = min(ans,mid);
        }
        else{
            l = mid + 1;
        }
    }
    if(ans == INF){
        ans = -1;
    }
    return ans;
}

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