Submission #592895

#	Time	Username	Problem	Language	Result	Execution time	Memory
592895		fuad27	Robots (IOI13_robots)	C++17	100 / 100	1963 ms	16552 KiB

robots

#include "robots.h"
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
	if(B == 0) {
		sort(X, X+A);
		int lo = 0, hi = 2*T;
		int res=-1;
		while(lo <= hi) {
			bool check=1;
			int mid = (lo+hi)/2;
			vector<int> v(A);
			for(int i = 0;i<T;i++) {
				int it = upper_bound(X, X+A, W[i])-X;
				if(it == A) {
					check=0;
					break;
				}
				v[it]++;
			}
			if(check) {
			for(int i = 0;i<A-1;i++) {
				if(v[i] > mid) {
					v[i+1]+=v[i]-mid;
					v[i]=mid;
				}
			}
			}
			if(v.back() > mid or !check) {
				lo = mid+1;
			}
			else {
				res=mid;
				hi=mid-1;
			}
		}
		return res;
	}
	else if(A == 0) {
		sort(Y, Y+B);
		int lo = 0, hi = 2*T;
		int res=-1;
		while(lo <= hi) {
			bool check=1;
			int mid = (lo+hi)/2;
			vector<int> v(B);
			for(int i = 0;i<T;i++) {
				int it = upper_bound(Y, Y+B, S[i])-Y;
				if(it == B) {
					check=0;
					break;
				}
				v[it]++;
			}
			if(check) {
				for(int i = 0;i<B-1;i++) {
					if(v[i] > mid) {
						v[i+1]+=v[i]-mid;
						v[i]=mid;
					}
				}
			}
			if(v.back() > mid or !check) {
				lo = mid+1;
			}
			else {
				res=mid;
				hi=mid-1;
			}
		}
		return res;
	}
	sort(X, X+A);
	sort(Y, Y+B);
	int lo = 0, hi = 2*T;
	vector<int> v[A];
	vector<int> vv;
	while(hi-lo > 1) { // (lo,hi]
		int mid = (lo+hi)/2, check=1;
		priority_queue<int> pq;
		vv.clear();
		for(int i = 0;i<T;i++) {
			int it = upper_bound(X, X+A, W[i])-X;
			if(it == A)vv.push_back(S[i]);
			else v[it].push_back(S[i]);
		}
		for(int i = 0;i<A;i++) {
			int cnt = 0;
			for(int j:v[i])pq.push(j);
			while(cnt < mid and pq.size()) {
				pq.pop();
				cnt++;
			}
			v[i].clear();
		}
		for(int i:vv)pq.push(i);
		for(int i = B-1;i>=0 and pq.size();i--) {
			int cnt = 0;
			while(cnt<mid and pq.size() && pq.top() < Y[i]){
				pq.pop();
				cnt++;
			}
		}
		check&=pq.empty();
		if(!check) {
			lo = mid;
		}
		else {
			hi = mid;
		}
	}
	if(hi == 2*T)return -1;
	return hi;
}

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