Submission #869504

#	Time	Username	Problem	Language	Result	Execution time	Memory
869504		teo_thrash	Robots (IOI13_robots)	C++14	76 / 100	1411 ms	23844 KiB

robots

// it is your desire to work hard
#include "robots.h"
#include<bits/stdc++.h>
#define pb push_back

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int maxn=1e5+3;
const int mod=1e9+7;

vector<pii> toys;
int n, A, B;
int to[maxn];

int weak[maxn], small[maxn];

bool moje(int x){
    priority_queue<int> q;

    int prev_to=-1;

    for(int i=0; i<A; i++){
        if(to[i]==-1) continue;
        for(int j=prev_to+1; j<=to[i] and j<n; j++) q.push(toys[j].second);

        int mahame=0;
        while(!q.empty() and mahame<x){ ///will put away X toys for time X
            mahame++;
            q.pop();
        }

        prev_to=to[i];
    }

    for(int i=prev_to+1; i<n; i++){
        q.push(toys[i].second);
    }

    for(int i=B-1; i>=0; i--){
        int mahame=0;
        while(mahame<x and !q.empty() and small[i]>q.top()){
            q.pop();
            mahame++;
        }
    }

    if(q.empty()) return true;
    return false;

}

int putaway(int a, int b, int t, int wk[], int sm[], int w[], int s[]) {
    n=t;
    A=a;
    B=b;

    for(int i=0; i<a; i++){
        weak[i]=wk[i];
    }
    for(int i=0; i<b; i++){
        small[i]=sm[i];
    }

    sort(weak, weak+a);
    sort(small, small+b);

    //cerr<<"nai-tegavi "<<weak[a-1]<<" "<<small[b-1]<<endl;

    for(int i=0; i<t; i++){
        toys.pb({w[i], s[i]});
    }

    sort(toys.begin(), toys.end());
   // cerr<<"nai-losha "<<toys[toys.size()-1].first<<" "<<toys[toys.size()-1].second<<endl;

    if(toys[toys.size()-1].first >= weak[a-1] and toys[toys.size()-1].second >= small[b-1]) return -1;

    //bs for each weak robot
    for(int i=0; i<a; i++){
        if(toys[0].first>=weak[i]){
            to[i]=-1;
            continue;
        }

        int l=0, r=t, m;

        while(l!=r-1){
            m=(l+r)/2;

            if(toys[m].first<weak[i]) l=m;
            else r=m;
        }


        to[i]=l;
        //cerr<<"to["<<i<<"]="<<l<<endl;
    }

    int l=0, r=1e6, m;
    while(l!=r-1){
        m=(l+r)/2;
        if(moje(m)){
           // cerr<<"s "<<m<<" moje"<<endl;
            r=m;
        }else{
            //cerr<<"s "<<m<<" ne moje"<<endl;
            l=m;
        }
    }

    return r;

}

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