# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
2349 |
2013-07-21T03:48:46 Z |
kriii |
Robots (IOI13_robots) |
C++ |
|
2441 ms |
13936 KB |
#include "robots.h"
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
vector<pair<int,int> > U;
priority_queue<int> H;
vector<int> P,Q;
bool chk(int v)
{
int i,j,c;
while (!H.empty()) H.pop();
for (i=j=0;i<P.size();i++){
while (j < U.size() && U[j].first < P[i]){
H.push(U[j].second); j++;
}
c = v;
while (c > 0 && !H.empty()){
H.pop(); c--;
}
}
for (;j<U.size();j++) H.push(U[j].second);
for (i=0;i<Q.size();i++){
c = v;
while (c > 0 && !H.empty()){
if (H.top() >= Q[i]) return false;
H.pop(); c--;
}
if (H.empty()) break;
}
return H.empty();
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
int i,x=0,y=0;
for (i=0;i<A;i++){
P.push_back(X[i]);
x = max(x,X[i]);
}
sort(P.begin(),P.end());
for (i=0;i<B;i++){
Q.push_back(Y[i]);
y = max(y,Y[i]);
}
sort(Q.rbegin(),Q.rend());
for (i=0;i<T;i++){
if (W[i] >= x && S[i] >= y) return -1;
U.push_back(make_pair(W[i],S[i]));
}
sort(U.begin(),U.end());
int l = 1, r = T, m = 1;
while (l < r){
m = (l + r) / 2;
if (chk(m)) r = m - 1;
else l = m + 1;
}
while (chk(m)) m--;
while (!chk(m)) m++;
return m;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
5220 KB |
Output is correct |
2 |
Correct |
0 ms |
5220 KB |
Output is correct |
3 |
Correct |
0 ms |
5220 KB |
Output is correct |
4 |
Correct |
0 ms |
5220 KB |
Output is correct |
5 |
Correct |
0 ms |
5220 KB |
Output is correct |
6 |
Correct |
0 ms |
5220 KB |
Output is correct |
7 |
Correct |
0 ms |
5220 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
5220 KB |
Output is correct |
2 |
Correct |
0 ms |
5220 KB |
Output is correct |
3 |
Correct |
0 ms |
5220 KB |
Output is correct |
4 |
Correct |
1767 ms |
13676 KB |
Output is correct |
5 |
Correct |
189 ms |
11628 KB |
Output is correct |
6 |
Correct |
48 ms |
6252 KB |
Output is correct |
7 |
Correct |
704 ms |
11628 KB |
Output is correct |
8 |
Correct |
1368 ms |
13676 KB |
Output is correct |
9 |
Correct |
2311 ms |
13676 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
5220 KB |
Output is correct |
2 |
Correct |
0 ms |
5220 KB |
Output is correct |
3 |
Correct |
0 ms |
5220 KB |
Output is correct |
4 |
Correct |
0 ms |
5220 KB |
Output is correct |
5 |
Correct |
0 ms |
5220 KB |
Output is correct |
6 |
Correct |
0 ms |
5220 KB |
Output is correct |
7 |
Correct |
0 ms |
5220 KB |
Output is correct |
8 |
Correct |
0 ms |
5220 KB |
Output is correct |
9 |
Correct |
0 ms |
5220 KB |
Output is correct |
10 |
Correct |
0 ms |
5220 KB |
Output is correct |
11 |
Correct |
0 ms |
5220 KB |
Output is correct |
12 |
Correct |
0 ms |
5220 KB |
Output is correct |
13 |
Correct |
0 ms |
5220 KB |
Output is correct |
14 |
Correct |
0 ms |
5220 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
5220 KB |
Output is correct |
2 |
Correct |
0 ms |
5220 KB |
Output is correct |
3 |
Correct |
0 ms |
5220 KB |
Output is correct |
4 |
Correct |
0 ms |
5220 KB |
Output is correct |
5 |
Correct |
0 ms |
5220 KB |
Output is correct |
6 |
Correct |
0 ms |
5220 KB |
Output is correct |
7 |
Correct |
0 ms |
5220 KB |
Output is correct |
8 |
Correct |
0 ms |
5220 KB |
Output is correct |
9 |
Correct |
0 ms |
5220 KB |
Output is correct |
10 |
Correct |
0 ms |
5220 KB |
Output is correct |
11 |
Correct |
0 ms |
5220 KB |
Output is correct |
12 |
Correct |
0 ms |
5220 KB |
Output is correct |
13 |
Correct |
0 ms |
5220 KB |
Output is correct |
14 |
Correct |
0 ms |
5220 KB |
Output is correct |
15 |
Correct |
0 ms |
5220 KB |
Output is correct |
16 |
Correct |
18 ms |
5352 KB |
Output is correct |
17 |
Correct |
20 ms |
5352 KB |
Output is correct |
18 |
Correct |
27 ms |
5352 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
5220 KB |
Output is correct |
2 |
Correct |
0 ms |
5220 KB |
Output is correct |
3 |
Correct |
0 ms |
5220 KB |
Output is correct |
4 |
Correct |
0 ms |
5220 KB |
Output is correct |
5 |
Correct |
0 ms |
5220 KB |
Output is correct |
6 |
Correct |
0 ms |
5220 KB |
Output is correct |
7 |
Correct |
0 ms |
5220 KB |
Output is correct |
8 |
Correct |
0 ms |
5220 KB |
Output is correct |
9 |
Correct |
0 ms |
5220 KB |
Output is correct |
10 |
Correct |
1750 ms |
13676 KB |
Output is correct |
11 |
Correct |
189 ms |
11628 KB |
Output is correct |
12 |
Correct |
49 ms |
6252 KB |
Output is correct |
13 |
Correct |
689 ms |
11628 KB |
Output is correct |
14 |
Correct |
1387 ms |
13676 KB |
Output is correct |
15 |
Correct |
0 ms |
5220 KB |
Output is correct |
16 |
Correct |
0 ms |
5220 KB |
Output is correct |
17 |
Correct |
0 ms |
5220 KB |
Output is correct |
18 |
Correct |
0 ms |
5220 KB |
Output is correct |
19 |
Correct |
0 ms |
5220 KB |
Output is correct |
20 |
Correct |
1 ms |
5220 KB |
Output is correct |
21 |
Correct |
20 ms |
5352 KB |
Output is correct |
22 |
Correct |
2329 ms |
13676 KB |
Output is correct |
23 |
Correct |
2319 ms |
13676 KB |
Output is correct |
24 |
Correct |
868 ms |
13936 KB |
Output is correct |
25 |
Correct |
693 ms |
11888 KB |
Output is correct |
26 |
Correct |
936 ms |
13936 KB |
Output is correct |
27 |
Correct |
1175 ms |
13936 KB |
Output is correct |
28 |
Correct |
1220 ms |
13936 KB |
Output is correct |
29 |
Correct |
2441 ms |
13936 KB |
Output is correct |