Submission #195630

#	Time	Username	Problem	Language	Result	Execution time	Memory
195630		jovan_b	Robots (IOI13_robots)	C++17	76 / 100	3058 ms	26340 KiB

robots

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

using namespace std;

typedef long long ll;

int a, b, t;
int x[100005];
int y[100005];
pair <int, int> toys[1000005];
bool used[1000005];

struct strukt{
    int w;
    int s;
    int ind;
    bool operator<(const strukt& a) const{
        return s < a.s;
    }
};

priority_queue <strukt> pq;

bool check(int k){
    while(!pq.empty()) pq.pop();
    for(int i=1; i<=t; i++) used[i] = 0;
    int j = 1;
    int cnt = 0;
    for(int i=1; i<=a; i++){
        while(j <= t /*&& toys[j].first < x[i]*/){
            if(toys[j].first >= x[i]) break;
            pq.push({toys[j].first, toys[j].second, j});
            j++;
        }
        int r = k;
        while(r-- && !pq.empty()){
            strukt g = pq.top();
            pq.pop();
            used[g.ind] = 1;
            cnt++;
        }
    }
    vector <int> vec;
    for(int i=1; i<=t; i++){
        if(!used[i]){
            vec.push_back(toys[i].second);
        }
    }
    sort(vec.begin(), vec.end());
    for(int i=b; i>=1; i--){
        int r = k;
        while(!vec.empty() && vec[vec.size()-1] < y[i] && r--){
            vec.pop_back();
        }
    }
    return vec.empty();
}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    a = A, b = B, t = T;
    for(int i=1; i<=t; i++){
        toys[i].first = W[i-1];
        toys[i].second = S[i-1];
    }
    sort(toys+1, toys+1+t);
    for(int i=1; i<=a; i++){
        x[i] = X[i-1];
    }
    sort(x+1, x+1+a);
    for(int i=1; i<=b; i++){
        y[i] = Y[i-1];
    }
    sort(y+1, y+1+b);
    int l = 1, r = T, res = T+1;
    while(l <= r){
        int mid = (l+r)/2;
        if(check(mid)){
            res = min(res, mid);
            r = mid-1;
        }
        else l = mid+1;
    }
    if(res == T+1) return -1;
    else return res;
}

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