# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
29352 |
2017-07-19T03:32:57 Z |
nibnalin |
Robots (IOI13_robots) |
C++14 |
|
3000 ms |
30896 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];
pair<int, int> A[maxn];
bool f(int x)
{
set<pair<int, int>> undone;
int ptr = 0;
for(int i = 0;i < a;i++)
{
while(ptr < t && A[ptr].first < X[i])
{
undone.insert({A[ptr].second, ptr});
ptr++;
}
int tmp = x;
while(!undone.empty() && tmp--)
{
pair<int, int> top = *undone.rbegin();
undone.erase(top);
}
}
while(ptr < t)
{
undone.insert({A[ptr].second, ptr});
ptr++;
}
for(int i = 0;i < b;i++)
{
int tmp = x;
while(!undone.empty() && undone.begin()->first < Y[i] && tmp--)
{
undone.erase(undone.begin());
}
}
return undone.empty();
}
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 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);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
14528 KB |
Output is correct |
2 |
Correct |
0 ms |
14528 KB |
Output is correct |
3 |
Correct |
0 ms |
14528 KB |
Output is correct |
4 |
Correct |
0 ms |
14528 KB |
Output is correct |
5 |
Correct |
0 ms |
14528 KB |
Output is correct |
6 |
Correct |
0 ms |
14528 KB |
Output is correct |
7 |
Correct |
0 ms |
14528 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
14528 KB |
Output is correct |
2 |
Correct |
0 ms |
14528 KB |
Output is correct |
3 |
Correct |
0 ms |
14528 KB |
Output is correct |
4 |
Execution timed out |
3000 ms |
30896 KB |
Execution timed out |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
14528 KB |
Output is correct |
2 |
Correct |
0 ms |
14528 KB |
Output is correct |
3 |
Correct |
0 ms |
14528 KB |
Output is correct |
4 |
Correct |
0 ms |
14528 KB |
Output is correct |
5 |
Correct |
0 ms |
14528 KB |
Output is correct |
6 |
Correct |
0 ms |
14528 KB |
Output is correct |
7 |
Correct |
0 ms |
14528 KB |
Output is correct |
8 |
Correct |
0 ms |
14528 KB |
Output is correct |
9 |
Correct |
0 ms |
14528 KB |
Output is correct |
10 |
Correct |
0 ms |
14528 KB |
Output is correct |
11 |
Correct |
0 ms |
14528 KB |
Output is correct |
12 |
Correct |
0 ms |
14528 KB |
Output is correct |
13 |
Correct |
0 ms |
14528 KB |
Output is correct |
14 |
Correct |
0 ms |
14528 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
14528 KB |
Output is correct |
2 |
Correct |
0 ms |
14528 KB |
Output is correct |
3 |
Correct |
0 ms |
14528 KB |
Output is correct |
4 |
Correct |
0 ms |
14528 KB |
Output is correct |
5 |
Correct |
0 ms |
14528 KB |
Output is correct |
6 |
Correct |
0 ms |
14528 KB |
Output is correct |
7 |
Correct |
0 ms |
14528 KB |
Output is correct |
8 |
Correct |
0 ms |
14528 KB |
Output is correct |
9 |
Correct |
0 ms |
14528 KB |
Output is correct |
10 |
Correct |
0 ms |
14528 KB |
Output is correct |
11 |
Correct |
0 ms |
14528 KB |
Output is correct |
12 |
Correct |
0 ms |
14528 KB |
Output is correct |
13 |
Correct |
0 ms |
14528 KB |
Output is correct |
14 |
Correct |
0 ms |
14528 KB |
Output is correct |
15 |
Correct |
0 ms |
14528 KB |
Output is correct |
16 |
Correct |
26 ms |
14792 KB |
Output is correct |
17 |
Correct |
26 ms |
14792 KB |
Output is correct |
18 |
Correct |
39 ms |
15056 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
14528 KB |
Output is correct |
2 |
Correct |
0 ms |
14528 KB |
Output is correct |
3 |
Correct |
0 ms |
14528 KB |
Output is correct |
4 |
Correct |
0 ms |
14528 KB |
Output is correct |
5 |
Correct |
0 ms |
14528 KB |
Output is correct |
6 |
Correct |
0 ms |
14528 KB |
Output is correct |
7 |
Correct |
0 ms |
14528 KB |
Output is correct |
8 |
Correct |
0 ms |
14528 KB |
Output is correct |
9 |
Correct |
0 ms |
14528 KB |
Output is correct |
10 |
Execution timed out |
3000 ms |
30896 KB |
Execution timed out |
11 |
Halted |
0 ms |
0 KB |
- |