Submission #109170

#	Time	Username	Problem	Language	Result	Execution time	Memory
109170		dantoh000	Robots (IOI13_robots)	C++14	76 / 100	3032 ms	14276 KiB

robots

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

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