Submission #404685

#	Time	Username	Problem	Language	Result	Execution time	Memory
404685		ly20	Robots (IOI13_robots)	C++17	90 / 100	3009 ms	48628 KiB

robots

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

using namespace std;

const int MAXN = 1123456;
//x -> w
//y -> s
int x[MAXN], y[MAXN];
pair <int, int> v[MAXN];
int n, a, b;
multiset <pair <int, int> > :: iterator it;
bool teste(int t) {
    if(b == 0) {
        int pt = a - 1, at = 0;
        for(int i = n - 1; i >= 0; i--) {
            if(v[i].first >= x[pt] || pt == -1) {
                return false;
            }
            else {
                at++;
                if(at == t) {
                    pt--;
                    at = 0;
                }
            }
        }
        return true;
    }
    multiset <pair <int, int> > sa;
    multiset <pair <int, int> > sb;
    multiset <int> sz;
    for(int i = 0; i < a; i++) sa.insert(make_pair(x[i], t));
    for(int i = 0; i < b; i++) sb.insert(make_pair(y[i], t));
    for(int i = n - 1; i >= 0; i--) {
        it = sa.upper_bound(make_pair(v[i].first, MAXN));
        sz.insert(v[i].second);
        if(it == sa.end()) {
            int a = *(sz.begin());
            sz.erase(sz.begin());
            it = sb.upper_bound(make_pair(a, MAXN));
            if(it == sb.end()) return false;
            else {
                pair <int, int> temp = *it;
                sb.erase(it);
                temp.second--;
                if(temp.second > 0) sb.insert(temp);
            }
        }
        else {
            pair <int, int> temp = *it;
            sa.erase(it);
            temp.second -= 1;
            if(temp.second > 0) {
                sa.insert(temp);
            }
        }
    }
    return true;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    n = T;
    a = A; b = B;
    for(int i = 0; i < T; i++) {
        v[i] = make_pair(W[i], S[i]);
    }
    sort(v, v + n);
    for(int i = 0; i < a; i++) x[i] = X[i];
    for(int i = 0; i < b; i++) y[i] = Y[i];
    sort(x, x + a); sort(y, y + b);
    int ini = 1, fim = MAXN;
    while(ini < fim) {
        int m = (ini + fim) / 2;
        if(teste(m)) {
            fim = m;
        }
        else ini = m + 1;
    }
    if(ini == MAXN) ini = -1;
    return ini;
}

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