Submission #1162099

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162099		AlgorithmWarrior	Robots (IOI13_robots)	C++20	100 / 100	1031 ms	13220 KiB

robots

#include <bits/stdc++.h>
#include "robots.h"

using namespace std;

int const MAX=1e6+5;

struct w_s{
    int w,s;
    bool operator<(w_s ot){
        return s>ot.s;
    }
}toy[MAX];

bool cmp(int a,int b){
    return a>b;
}

bool check(int days,int X[],int Y[],int A,int B,int T){
    map<int,int>mep;
    int i;
    for(i=0;i<A;++i)
        if(1LL*i*days<T)
            mep[X[i]]+=days;
    vector<int>v;
    for(i=0;i<T;++i)
        if(mep.upper_bound(toy[i].w)->second==0)
            v.push_back(toy[i].s);
        else{
            int nr=mep.upper_bound(toy[i].w)->first;
            --mep[nr];
            if(mep[nr]==0)
                mep.erase(nr);
        }
    if(1LL*B*days<(int)v.size())
        return 0;
    for(i=0;i*days<(int)v.size();++i)
        if(v[i*days]>=Y[i])
            return 0;
    return 1;
}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    sort(X,X+A,cmp);
    sort(Y,Y+B,cmp);
    int i;
    for(i=0;i<T;++i)
        toy[i]={W[i],S[i]};
    sort(toy,toy+T);
    for(i=0;i<T;++i)
        if(toy[i].w>=X[0] && toy[i].s>=Y[0])
            return -1;
    /// (]
    int st=0,dr=T;
    while(dr-st>1){
        int mij=(st+dr)/2;
        if(check(mij,X,Y,A,B,T))
            dr=mij;
        else
            st=mij;
    }
    return dr;
}

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