Submission #1310267

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310267		StefanSebez	Robots (IOI13_robots)	C++20	90 / 100	3096 ms	9232 KiB

robots

//Hall theorem
#include "robots.h"
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
#define mp make_pair
vector<int>X,Y;
vector<pair<int,int>>Z;
int putaway(int A, int B, int T, int X1[], int Y1[], int W[], int S[]) {
    for(int i=0;i<A;i++)X.pb(X1[i]);X.pb(0);
    sort(X.begin(),X.end());
    for(int i=0;i<B;i++)Y.pb(Y1[i]);Y.pb(0);
    sort(Y.begin(),Y.end());
    for(int i=0;i<T;i++)Z.pb({W[i],S[i]});
    sort(Z.begin(),Z.end());
    int res=0;
    int num[B+1]={0};
    for(int i=A,k=T-1;i>=0&&res!=-1;i--){
        while(k>=0&&Z[k].fi>=X[i]){
            int lb=upper_bound(Y.begin(),Y.end(),Z[k].se)-Y.begin()-1;
            num[lb]++;
            k--;
        }
        for(int j=B,x=0;j>=0&&res!=-1;j--){
            int y=A-i+B-j;
            x+=num[j];
            if(y==0){if(x>0)res=-1;continue;}
            res=max(res,(x+y-1)/y);
        }
    }
    return res;
}

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