Submission #404686

#	Time	Username	Problem	Language	Result	Execution time	Memory
404686		peuch	Robots (IOI13_robots)	C++17	14 / 100	277 ms	20324 KiB

robots

#include "robots.h"
#include<bits/stdc++.h>
using namespace std;

const int MAXN = 1e6 + 10;

int n, m, t;
int x[MAXN], y[MAXN];
int freq[MAXN];

int bb();
bool test(int val);

struct point{
	int x, y, xID, yID;
	point(int _x = 0, int _y = 0, int _xID = 0, int _yID = 0){
		x = _x, y = _y, xID = _xID, yID = _yID;
	}
	bool operator <(point a){
		if(xID == a.xID) return yID < a.yID;
		return xID < a.xID;
	}
} v[MAXN];

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    n = A, m = B, t = T;
    for(int i = 0; i < n; i++)
    	x[i] = X[i];
    for(int i = 0; i < m; i++)
    	y[i] = Y[i];
    sort(x, x + n);
    sort(y, y + m);
    
    for(int i = 0; i < t; i++){
    	int auxX = upper_bound(x, x + n, W[i]) - x;
    	auxX = n - auxX - 1;
    	int auxY = upper_bound(y, y + m, S[i]) - y;
    	auxY = m - auxY - 1;
    	v[i] = point(W[i], S[i], auxX, auxY);
    }
    	
    reverse(x, x + n);
    reverse(y, y + m);
    
    sort(v, v + t);
	return bb();
}

int bb(){
	int ini = 1, fim = t;
	if(!test(t + 1)) return -1;
	while(ini != fim){
		int mid = (ini + fim) >> 1;
		if(test(mid)) fim = mid;
		else ini = mid + 1;
	}
	return ini;
}

bool test(int val){
	
	if(m == 0){
		int naoPego = 0;
		for(int i = 0; i < n; i++){
			if(v[naoPego].x >= x[i]) return 0;
			naoPego += val;
			if(naoPego >= t) return 1; 
		}
		return 0;
	}
	
	for(int i = 0; i < m; i++)
		freq[i] = 0;
	
	int it1 = 0;
	multiset<int> sobra;
	multiset<int> pegando;
	int podePega = val;
		
	while(it1 != t && v[it1].xID == -1)
		freq[v[it1++].yID + 1]++;
	
	for(int i = 0; i < n; i++){
		while(it1 != t && v[it1].xID == i && podePega)
			podePega--, it1++;
		while(it1 != t && v[it1].xID == i)
			freq[v[it1++].yID + 1]++;
		podePega += val;
	}
	
	podePega = val;
	if(freq[0] > 0) return 0;
	for(int i = 0; i < m; i++){
		if(freq[i + 1] > podePega) return 0;
		podePega += val - freq[i];
	}
	return 1;
}

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