Submission #515582

#	Time	Username	Problem	Language	Result	Execution time	Memory
515582		AdamGS	Robots (IOI13_robots)	C++17	0 / 100	2 ms	1484 KiB

robots

#include "robots.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1e6+7, LIM2=5e4+7;
int X[LIM2], Y[LIM2], W[LIM], S[LIM], ile[LIM2], A, B, n;
vector<int>V[LIM2];
bool f(int x) {
    rep(i, B) ile[i]=0;
    priority_queue<int>q;
    int p=0;
    for(int i=A-1; i>=0; --i) {
        for(auto j : V[i]) q.push(-j);
        p+=x;
        p-=V[i].size();
        while(p<0) {
            ++ile[-q.top()];
            q.pop();
            ++p;
        }
    }
    p=0;
    for(int i=B-1; i>=0; --i) {
        p+=x;
        p-=ile[i];
        if(p<0) return false;
    }
    return true;
}
int putaway(int Ai, int Bi, int Ti, int Xi[], int Yi[], int Wi[], int Si[]) {
    A=Ai;
    B=Bi;
    n=Ti;
    rep(i, A) X[i]=Xi[i];
    rep(i, B) Y[i]=Yi[i];
    rep(i, n) {
        W[i]=Wi[i];
        S[i]=Si[i];
    }
    sort(X, X+A);
    sort(Y, Y+B);
    rep(i, n) if(W[i]>=X[A-1] && S[i]>=Y[B-1]) return -1;
    rep(i, n) {
        int p=0, k=A-1;
        while(p<k) {
            int sr=(p+k)/2;
            if(X[sr]<=W[i]) p=sr+1; else k=sr;
        }
        W[i]=p;
        p=0; k=B-1;
        while(p<k) {
            int sr=(p+k)/2;
            if(Y[sr]<=S[i]) p=sr+1; else k=sr;
        }
        S[i]=p;
    }
    rep(i, n) V[W[i]].pb(S[i]);
    int p=1, k=n;
    while(p<k) {
        int sr=(p+k)/2;
        if(f(sr)) k=sr; else p=sr+1;
    }
    return p;
}

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