Submission #659410

#	Time	Username	Problem	Language	Result	Execution time	Memory
659410		angelo_torres	Robots (IOI13_robots)	C++17	28 / 100	190 ms	8896 KiB

robots

#include <bits/stdc++.h>
#include "robots.h"
#define sz(v) (int) v.size() 
#define ff first
#define ss second

using namespace std;
typedef pair<int,int> ii;

vector<int> a,b;
vector<ii> t;

bool go(int mn){
    int mlx = mn, ix = sz(a)-1, mly = mn, iy = sz(b)-1;
    for(int i = sz(t)-1; i >= 0; --i){
        int wi = t[i].ff, si = t[i].ss;
        if(ix >= 0 && a[ix] > wi){
            mlx--;
            if(mlx == 0) mlx = mn, ix--;
            continue;
        }
        if(iy >= 0 && b[iy] > si){
            mly--;
            if(mly == 0) mly = mn, iy--;
            continue;
        }
        return false;
    }
    return true;
}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]){
    // A -> X -> W[i] < X[i]
    // B -> Y -> S[i] < Y[i]
    for(int i = 0; i < A; ++i) a.push_back(X[i]);
    for(int i = 0; i < B; ++i) b.push_back(Y[i]);
    sort(a.begin(),a.end()), sort(b.begin(),b.end());
    for(int i = 0; i < T; ++i) t.push_back({W[i],S[i]});
    sort(t.begin(),t.end());
    int l = 0, r = 1000001;
    // [l,r>
    while(r-l > 1){
        int md = (l+r)>>1;
        if(!go(md)) l = md;
        else r = md;
    }
    if(r == 1000001) return -1;
    return r;
}

// int main(){
//     int A,B,T;
//     cin >> A >> B >> T;
//     int X[A+10],Y[B+10],W[T+10],S[T+10];
//     for(int i = 0; i < A; ++i) cin >> X[i];
//     for(int i = 0; i < B; ++i) cin >> Y[i];
//     for(int i = 0; i < T; ++i) cin >> W[i] >> S[i];
//     cout << putaway(A,B,T,X,Y,W,S) << "\n";
// }

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