Submission #1285606

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285606		enzy	Robots (IOI13_robots)	C++20	0 / 100	1 ms	580 KiB

robots

#include "robots.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
int x[maxn], y[maxn], w[maxn], s[maxn];
bool check(int at, int a, int b, int n){
    vector<pair<int,int>>v;
    for(int i=1;i<=n;i++) v.push_back({w[i],s[i]});
    sort(v.begin(),v.end()); reverse(v.begin(),v.end());
    multiset<int>ms;
    //cout << "weak: " << endl;
    for(int i=1;i<=a;i++){
        //cout << i << ": ";
        while(v.size()&&v.back().first<=x[i]){
            ms.insert(v.back().second);
            v.pop_back();
        }
        int qtd=at;
        while(qtd&&ms.size()){
            qtd--;
            auto f=ms.end(); f--;
            //cout << *f << " ";
            ms.erase(f);
        }
        //cout << endl;
    }
    while(v.size()){
        ms.insert(v.back().second);
        v.pop_back();
    }
    //cout << endl;
    //cout << "small: " << endl;
    for(int i=1;i<=b;i++){
        //cout << i << ": ";
        int qtd=at;
        while(qtd&&ms.size()){
            auto f=ms.begin();
            int aux=*f;
            if(aux>y[i]) break;
            //cout << aux << " ";
            qtd--;
            ms.erase(ms.begin());
        }
        //cout << endl;
    }
    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++) w[i]=W[i-1];
    for(int i=1;i<=T;i++) s[i]=S[i-1];
    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: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 25
• Subtask 4: 0 / 37
• Subtask 5: 0 / 10