oj.uz

Submission #29354

# Submission time Handle Problem Language Result Execution time Memory
29354 2017-07-19T05:14:17 Z nibnalin Robots (IOI13_robots) C++14
28 / 100
 359 ms 23576 KB 
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>
#include "robots.h"
using namespace std;

const int maxn = int(1e6)+5, maxs = int(5e4)+5, inf = int(1e9)+5;

int t, a, b, X[maxs], Y[maxs], undone[maxn];
pair<int, int> A[maxn];
vector<int> guys[maxs];

bool f(int x)
{
	int undone = 0;
	pair<int, int> ptr = {0, x};

	for(int i = 0;i < a;i++)
	{
		if(int(guys[i].size()) < x)
		{
			int tmp = x-int(guys[i].size());
			undone = max(0, undone-tmp);
		}
		else
		{
			for(int j = 0;j < int(guys[i].size())-x;j++)
			{
				if(ptr.first == b)
				{
					undone++;
					continue;
				}
				
				while(ptr.first < b && (guys[i][j] >= Y[ptr.first] || !ptr.second)) ptr.first++, ptr.second = x;
				if(ptr.first == b)
				{
					undone++;
					continue;
				}
				
				ptr.second--;
			}
		}
	}

	for(int j = 0;j < int(guys[a].size());j++)
	{
		if(ptr.first == b)
		{
			undone++;
			continue;
		}
				
		while(ptr.first < b && (guys[a][j] >= Y[ptr.first] || !ptr.second)) ptr.first++, ptr.second = x;
		if(ptr.first == b)
		{
			undone++;
			continue;
		}
				
		ptr.second--;
	}

	//cout << x << " " << undone << "\n";
	return !undone;
}


int putaway(int _A, int _B, int _T, int _X[], int _Y[], int _W[], int _S[])
{
	a = _A, b = _B, t = _T;
	for(int i = 0;i < t;i++) A[i] = {_W[i], _S[i]};
	for(int i = 0;i < a;i++) X[i] = _X[i];
	for(int i = 0;i < b;i++) Y[i] = _Y[i];
	sort(A, A+t), sort(X, X+a), sort(Y, Y+b);

	int ptr = 0;
	for(int i = 0;i < a;i++)
	{
		while(ptr < t && A[ptr].first < X[i])
		{
			guys[i].push_back(A[ptr].second);
			ptr++;
		}
		sort(guys[i].begin(), guys[i].end());
	}
	while(ptr < t)
	{
		guys[a].push_back(A[ptr].second);
		ptr++;
	}
	sort(guys[a].begin(), guys[a].end());

	int L = 1, R = t+1, ans = inf;
	
	while(L <= R)
	{
		int mid = (L+R)/2;
		if(f(mid)) R = mid-1, ans = min(ans, mid);
		else L = mid+1;
	}
	return ((ans > t+1)?-1:ans);
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 19604 KB Output is correct
2 Correct 0 ms 19604 KB Output is correct
3 Correct 0 ms 19604 KB Output is correct
4 Correct 0 ms 19604 KB Output is correct
5 Correct 0 ms 19604 KB Output is correct
6 Correct 0 ms 19604 KB Output is correct
7 Correct 0 ms 19604 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 19604 KB Output is correct
2 Correct 0 ms 19604 KB Output is correct
3 Correct 0 ms 19604 KB Output is correct
4 Correct 359 ms 23576 KB Output is correct
5 Correct 299 ms 22760 KB Output is correct
6 Correct 36 ms 21188 KB Output is correct
7 Correct 236 ms 23564 KB Output is correct
8 Correct 336 ms 22772 KB Output is correct
9 Correct 293 ms 22760 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 19604 KB Output is correct
2 Correct 0 ms 19604 KB Output is correct
3 Correct 0 ms 19604 KB Output is correct
4 Correct 0 ms 19604 KB Output is correct
5 Correct 0 ms 19604 KB Output is correct
6 Correct 0 ms 19604 KB Output is correct
7 Correct 0 ms 19604 KB Output is correct
8 Correct 0 ms 19604 KB Output is correct
9 Correct 0 ms 19604 KB Output is correct
10 Correct 0 ms 19604 KB Output is correct
11 Correct 0 ms 19604 KB Output is correct
12 Incorrect 0 ms 19604 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 19604 KB Output is correct
2 Correct 0 ms 19604 KB Output is correct
3 Correct 0 ms 19604 KB Output is correct
4 Correct 0 ms 19604 KB Output is correct
5 Correct 0 ms 19604 KB Output is correct
6 Correct 0 ms 19604 KB Output is correct
7 Correct 0 ms 19604 KB Output is correct
8 Correct 0 ms 19604 KB Output is correct
9 Correct 0 ms 19604 KB Output is correct
10 Correct 0 ms 19604 KB Output is correct
11 Correct 0 ms 19604 KB Output is correct
12 Correct 0 ms 19604 KB Output is correct
13 Incorrect 0 ms 19604 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 19604 KB Output is correct
2 Correct 0 ms 19604 KB Output is correct
3 Correct 0 ms 19604 KB Output is correct
4 Correct 0 ms 19604 KB Output is correct
5 Correct 0 ms 19604 KB Output is correct
6 Correct 0 ms 19604 KB Output is correct
7 Correct 0 ms 19604 KB Output is correct
8 Correct 0 ms 19604 KB Output is correct
9 Correct 0 ms 19604 KB Output is correct
10 Correct 296 ms 23576 KB Output is correct
11 Correct 329 ms 22760 KB Output is correct
12 Correct 33 ms 21188 KB Output is correct
13 Correct 259 ms 23564 KB Output is correct
14 Correct 296 ms 22772 KB Output is correct
15 Correct 0 ms 19604 KB Output is correct
16 Correct 0 ms 19604 KB Output is correct
17 Correct 0 ms 19604 KB Output is correct
18 Incorrect 0 ms 19604 KB Output isn't correct
19 Halted 0 ms 0 KB -