Submission #1285609

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285609		enzy	Robots (IOI13_robots)	C++20	76 / 100	3095 ms	32052 KiB

robots

#include "robots.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
int x[maxn], y[maxn];
vector<pair<int,int>>v;
bool check(int at, int a, int b, int n){
    multiset<int>ms;
    int id=0;
    for(int i=1;i<=a;i++){
        while(id<v.size()&&v[id].first<x[i]){
            ms.insert(v[id].second);
            id++;
        }
        int qtd=at;
        while(qtd&&ms.size()){
            qtd--;
            auto f=ms.end(); f--;
            ms.erase(f);
        }
    }
    while(id<v.size()){
        ms.insert(v[id].second);
        id++;
    }
    for(int i=1;i<=b;i++){
        int qtd=at;
        while(qtd&&ms.size()){
            auto f=ms.begin();
            int aux=*f;
            if(aux>=y[i]) break;
            qtd--;
            ms.erase(ms.begin());
        }
    }
    if(ms.size()) return false;
    else return true;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]){
    int l=1, r=T;
    for(int i=1;i<=A;i++) x[i]=X[i-1];
    for(int i=1;i<=B;i++) y[i]=Y[i-1];
    for(int i=1;i<=T;i++) v.push_back({W[i-1],S[i-1]});
    sort(v.begin(),v.end());
    sort(x+1,x+1+A); sort(y+1,y+1+B);
    while(l<r){
        int mid=(l+r)/2;
        if(check(mid,A,B,T)) r=mid;
        else l=mid+1;
    }
    if(check(l,A,B,T)) return l;
    else return -1;
}

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