Submission #109165

#	Time	Username	Problem	Language	Result	Execution time	Memory
109165		dantoh000	Robots (IOI13_robots)	C++14	0 / 100	3021 ms	14040 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){
        //printf("toy %d weight %d robot %d\n",v[curT],W[v[curT]],curA);
        if (X[curA] <= W[v[curT]]){
            int num = 0;
            while (num++ < x && pq.size()){
                //printf("robot %d takes %d weight %d\n",curA,pq.top().second,pq.top().first);
                pq.pop();
            }
            curA++;
        }
        else{
            pq.push(S[v[curT]]);
            curT++;
        }
    }
    while (curA++ < A){
        int num = 0;
        while (num++ < x && pq.size()){
            //printf("robot %d takes %d size %d\n",curA,pq.top().second,pq.top().first);
            pq.pop();
        }
    }
    while (curT < T){
        //printf("toy %d not taken by weight\n",v[curT]);
        pq.push(S[v[curT++]]);
    }
    int curB = B-1;
    while (curB && pq.size()){
        //printf("toy %d size %d robot %d\n",v2[curT],S[v2[curT]],curB);
        if (Y[curB] <= pq.top()) return false;
        else{
            int num = 0;
            while (num++ < x && pq.size()){
                //printf("robot %d takes %d size %d\n",curB,pq.top().second,pq.top().first);
                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: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 25
• Subtask 4: 0 / 37
• Subtask 5: 0 / 10