Submission #109173

#	Time	Username	Problem	Language	Result	Execution time	Memory
109173		dantoh000	Robots (IOI13_robots)	C++14	100 / 100	2398 ms	28852 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
int a,b,t;
int x[50005], y[50005];
int w[1000005], s[1000005];
vector<int> v(1000005);
bool cmpw(int a, int b){
    return w[a] < w[b];
}
bool cando(int pp){
    //printf("\t\t\t\tTesting %d\n",pp);
    int curT = 0, curA = 0;
    priority_queue<int> pq;
    while (curT < t && curA < a){
        if (x[curA] <= w[v[curT]]){
            int num = 0;
            while (num++ < pp && pq.size()){
                //printf("popping %d\n",pq.top());
                pq.pop();
            }
            curA++;
        }
        else{
            //printf("pushing %d\n",s[v[curT]]);
            pq.push(s[v[curT]]);
            curT++;
        }
    }
    //printf("%d %d %d\n",pq.size(),curA,a);
    for (long long i = 0; i < (long long)(a-curA)*pp && pq.size(); i++){
        //printf("popping %d\n",pq.top());
        pq.pop();
    }
    //printf("%d %d\n",curT,t);
    while (curT < t){
        //printf("pushing %d\n",s[v[curT]]);
        pq.push(s[v[curT++]]);
    }
    int curB = b-1;
    //printf("%d ",pq.size());
    while (curB >= 0 && pq.size()){
        //printf("%d %d\n",y[curB],pq.top());
        if (y[curB] <= pq.top()) return false;
        else{
            int num = 0;
            while (num++ < pp && pq.size()){
                //printf("popping %d\n",pq.top());
                //printf("robot %d takes size %d\n",curB,pq.top());
                pq.pop();
            }
            curB--;
        }
    }
    return pq.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 = 0; i < t; i++){
        w[i] = W[i];
        s[i] = S[i];
    }
    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 lo = 0, hi = t+1;
	v.resize(t);
	for (int i = 0; i < t; i++) v[i] = i;
	sort(v.begin(),v.end(),cmpw);
	while (lo + 1 < hi){
        //printf("%d %d\n",lo,hi);
        int mid = (lo+hi)/2;
        if (cando(mid)){
            hi = mid;
        }
        else lo = mid;
	}
	if (lo + 1 == hi){
        //printf("%d %d\n",lo,hi);
        if (cando(lo)) hi = lo;
        else lo = hi;
	}
	if (lo == t+1) return -1;
	return lo;
}

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