제출 #515615

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
515615		AdamGS	Robots (IOI13_robots)	C++17	76 / 100	264 ms	13308 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;
const int INF=1e9+7;
int X[LIM2], Y[LIM2], W[LIM], S[LIM], ile[LIM2], ile2[LIM2], A, B, n;
vector<int>V[LIM2];
bool f(int x) {
    rep(i, B+1) ile[i]=ile2[i]=0;
    int p=0, z=0;
    for(int i=A; i>=0; --i) {
        for(auto j : V[i]) ++ile2[j];
        p-=V[i].size();
        while(p<0) {
            z+=-p;
            p=0;
        }
        p+=x;
    }
    rep(i, B+1) {
        ile[i]+=min(ile2[i], z);
        z-=min(ile2[i], z);
    }
    p=0;
    for(int i=B; i>=0; --i) {
        p-=ile[i];
        if(p<0) return false;
        p+=x;
    }
    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;
    X[A]=2*INF;
    Y[B]=2*INF;
    rep(i, n) {
        int p=0, k=A;
        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;
        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: 14 / 14
• Subtask 2: 0 / 14
• Subtask 3: 25 / 25
• Subtask 4: 37 / 37
• Subtask 5: 0 / 10