제출 #638113

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
638113		beaconmc	로봇 (IOI13_robots)	C++14	100 / 100	1574 ms	39820 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

typedef long long ll;
using namespace std;
using namespace __gnu_pbds;

#define FOR(i, x, y) for(ll i=x; i<y; i++)
#define FORNEG(i, x, y) for(ll i=x; i>y; i--)
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)



int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    sort(X,X+A);
    sort(Y,Y+B);
    FOR(i,0,T){
        W[i]++;
        S[i]++;
    }


    FOR(i,0,T){
        if (W[i] > X[A-1] && S[i] > Y[B-1]){
            return -1;
        }
    }

    FOR(i,0,T){
        W[i] = lower_bound(X,X+A, W[i])-X;
    }

    vector<pair<ll,ll>> realsus;
    FOR(i,0,T){
        realsus.push_back(make_pair(W[i],-S[i]));
    }
    sort(realsus.begin(), realsus.end());
    reverse(realsus.begin(),realsus.end());



    



    const auto check = [&](int k) -> bool{
        priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater_equal<pair<ll,ll>>> sus;
        priority_queue<ll, vector<ll>, greater_equal<ll>> sus2;
        ll ii = realsus.size()-1;

        FOR(i,0,A){
            while (ii>=0 && realsus[ii].first <= i){
                sus.push(make_pair(realsus[ii].second, realsus[ii].second));
                ii--;
            }
            

            ll cnt = 0;
            while (sus.size()!=0){
                if (cnt==k) break;
                cnt++;
                sus.pop();
            }

        }

        
        while (sus.size()!=0){
            ll temp = sus.top().second;
            sus.pop();
            sus2.push(-temp);
        }

        while (ii>=0){
            sus2.push(-realsus[ii].second);
            ii--;
        }



        FOR(i,0,B){
            ll cnt = 0;
            while (sus2.size()!=0){
                if (cnt==k) break;
                ll temp = sus2.top();
                if (temp > Y[i]) break;
                cnt++;
                sus2.pop();
            }


        }





        if (sus2.size()) return 0;
        else return 1;

    };

    ll lo = 1;
    ll hi = T+2;




    while (lo<hi){
        
        ll mid = lo + (hi - lo) / 2;
        if (check(mid)) hi = mid;

        else lo = mid + 1;
        
    }

    return lo;



}

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