Submission #135795

#	Time	Username	Problem	Language	Result	Execution time	Memory
135795		mirbek01	Robots (IOI13_robots)	C++11	100 / 100	2884 ms	40320 KiB

robots

#include "robots.h"
//#include "grader.cpp"
#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 2;

int n, used[N];
vector <int> x, y, w, s;
vector < pair <int, int> > v1, v2;

bool check(int c){
	memset(used, 0, sizeof(used));
	int pt = -1, sz = (int)x.size();
	priority_queue< pair <int, int> > q;
	for(int i = 0; i < sz; i ++){
		while(pt + 1 < n && v1[pt + 1].first < x[i]){
			pt ++;
			q.push( {s[ v1[pt].second ], v1[pt].second} );
		}
		int cn = c;
		while(cn > 0 && !q.empty()){
			cn --;
			int id = q.top().second;
			q.pop();	
			used[id] = 1;
		}
	}
	stack <int> stk;
	sz = y.size();
	pt = -1;
	for(int i = 0; i < sz; i ++){
		while(pt + 1 < n && v2[pt + 1].first < y[i]){
			pt ++;
			if(!used[ v2[pt].second ])
				stk.push( v2[pt].second );
		}
		int cn = c;
		while(cn > 0 && !stk.empty()){
			used[ stk.top() ] = 1;
			stk.pop();
			cn --;
		}
	}
	for(int i = 0; i < n; i ++)
		if(!used[i])
			return 0;
	return 1;
}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    for(int i = 0; i < A; i ++)
		x.emplace_back(X[i]);
	for(int i = 0; i < B; i ++)
		y.emplace_back(Y[i]);
	n = T;
	for(int i = 0; i < T; i ++){
		w.emplace_back(W[i]);
		s.emplace_back(S[i]);
		v1.emplace_back(W[i], i);
		v2.emplace_back(S[i], i);
	}
	sort(v1.begin(), v1.end());
	sort(v2.begin(), v2.end());
	sort(x.begin(), x.end());
	sort(y.begin(), y.end());
    int lo = 1, hi = T;
    if(!check(T)) return -1;
    while(lo <= hi){
		int md = (lo + hi) >> 1;
		if(check(md))
			hi = md - 1;
		else 
			lo = md + 1;
	}
	return hi + 1;
}

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