Submission #393475

#	Time	Username	Problem	Language	Result	Execution time	Memory
393475		Vladth11	Robots (IOI13_robots)	C++14	100 / 100	2173 ms	35868 KiB

robots

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define debug(x) cerr << #x << " " << x << "\n"
#define debug_with_space(x) cerr << #x << " " << x << " "
#include "robots.h"
 
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <long double, pii> muchie;
typedef tree <ll, null_type, less_equal <ll>, rb_tree_tag, tree_order_statistics_node_update> OST;
 
const ll NMAX = 1000001;
const ll INF = (1LL << 60);
const ll MOD = 666013;
const ll BLOCK = 225;
const ll base = 31;
const ll nr_of_bits = 8;
 
vector <pii> v, cop;
int a, b, t;
int x[NMAX];
int y[NMAX];
int w[NMAX];
int s[NMAX];
 
bool cmp(pii a, pii b) {
    return a.second > b.second;
}
 
bool OK(int time) {
    cop = v;
    priority_queue <int> pq;
    for(int i = 0; i < a; i++) {
        while(v.size() && v.back().first < x[i]) {
            pq.push(v.back().second);
            v.pop_back();
        }
        int cc = time;
        while(cc-- && pq.size()) {
            pq.pop();
        }
    }
    while(pq.size()) {
        v.push_back({0, pq.top()});
        pq.pop();
    }
    sort(v.begin(), v.end(), cmp);
    for(int i = 0; i < b; i++) {
      	int cc = time;
        while(v.size() && v.back().second < y[i] && cc--) {
            v.pop_back();
        }
    }
    int ok = !(v.size());
    v = cop;
    return ok;
}
 
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    v.clear();
    a = A;
    b = B;
    t = T;
    for(int i = 0; i < A; i++)
        x[i] = X[i];
    for(int i = 0; i < B; i++)
        y[i] = Y[i];
    for(int i = 0; i < T; i++) {
        w[i] = W[i];
        s[i] = S[i];
    }
    for(int i = 0; i < T; i++) {
        v.push_back({W[i], S[i]});
    }
    sort(x, x + A);
    sort(y, y + B);
    sort(v.begin(), v.end());
    reverse(v.begin(), v.end());
    int r = 0, pas = (1 << 20);
    while(pas) {
        if(!OK(r + pas)) {
            r += pas;
        }
        pas /= 2;
    }
    if(OK(r + 1))
        return r + 1;
    return -1;
}

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