# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
982888 |
2024-05-15T00:04:41 Z |
hyakup |
Robots (IOI13_robots) |
C++17 |
|
3000 ms |
25052 KB |
#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
const int inf = 2e9 + 10;
vector<int> wbots, sbots;
struct Toy{
int w, s; Toy( int w, int s ): w(w), s(s) {}
bool operator < ( Toy t ){ return (( s == t.s ) ? w > t.w : s > t.s ); }
}; vector<Toy> toys;
bool check( int k ){
multiset<pair<int, int>> s;
for( int x : wbots ) s.insert({ x - 1, k });
int i = 0;
for( Toy cur : toys ){
for( i; i < sbots.size() && sbots[i] > cur.s; i++ ) s.insert({ inf, k });
auto it = s.lower_bound({ cur.w, 0 });
if( it == s.end() ) return false;
auto [val, qtd] = *it;
s.erase(it);
if( qtd > 1 ) s.insert({ val, qtd - 1 });
}
return true;
}
int bs(){
int l = 1, r = toys.size() + 1;
while( l < r ){
int mid = ( l + r )/2;
if( check(mid) ) r = mid;
else l = mid + 1;
}
return ( r == toys.size() + 1 ) ? -1 : r;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
for( int i = 0; i < A; i++ ) wbots.push_back(X[i]);
for( int i = 0; i < B; i++ ) sbots.push_back(Y[i]);
for( int i = 0; i < T; i++ ) toys.push_back( Toy( W[i], S[i] ) );
sort( wbots.begin(), wbots.end() );
sort( sbots.rbegin(), sbots.rend() );
sort( toys.begin(), toys.end() );
return bs();
}
Compilation message
robots.cpp: In function 'bool check(int)':
robots.cpp:18:10: warning: statement has no effect [-Wunused-value]
18 | for( i; i < sbots.size() && sbots[i] > cur.s; i++ ) s.insert({ inf, k });
| ^
robots.cpp:18:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
18 | for( i; i < sbots.size() && sbots[i] > cur.s; i++ ) s.insert({ inf, k });
| ~~^~~~~~~~~~~~~~
robots.cpp: In function 'int bs()':
robots.cpp:35:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Toy>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | return ( r == toys.size() + 1 ) ? -1 : r;
| ~~^~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
1 ms |
4444 KB |
Output is correct |
3 |
Correct |
1 ms |
4444 KB |
Output is correct |
4 |
Correct |
2 ms |
4444 KB |
Output is correct |
5 |
Correct |
1 ms |
4444 KB |
Output is correct |
6 |
Correct |
1 ms |
4444 KB |
Output is correct |
7 |
Correct |
1 ms |
4444 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
1 ms |
4444 KB |
Output is correct |
3 |
Correct |
1 ms |
4444 KB |
Output is correct |
4 |
Correct |
1412 ms |
21760 KB |
Output is correct |
5 |
Correct |
589 ms |
21176 KB |
Output is correct |
6 |
Correct |
357 ms |
8784 KB |
Output is correct |
7 |
Correct |
2973 ms |
19488 KB |
Output is correct |
8 |
Correct |
2157 ms |
21640 KB |
Output is correct |
9 |
Correct |
734 ms |
21372 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4440 KB |
Output is correct |
2 |
Correct |
2 ms |
4444 KB |
Output is correct |
3 |
Correct |
2 ms |
4444 KB |
Output is correct |
4 |
Correct |
2 ms |
4444 KB |
Output is correct |
5 |
Correct |
2 ms |
4444 KB |
Output is correct |
6 |
Correct |
2 ms |
4444 KB |
Output is correct |
7 |
Correct |
3 ms |
4444 KB |
Output is correct |
8 |
Correct |
1 ms |
4540 KB |
Output is correct |
9 |
Correct |
1 ms |
4444 KB |
Output is correct |
10 |
Correct |
1 ms |
4444 KB |
Output is correct |
11 |
Correct |
1 ms |
4444 KB |
Output is correct |
12 |
Correct |
1 ms |
4444 KB |
Output is correct |
13 |
Correct |
1 ms |
4532 KB |
Output is correct |
14 |
Correct |
1 ms |
4440 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4440 KB |
Output is correct |
2 |
Correct |
1 ms |
4444 KB |
Output is correct |
3 |
Correct |
2 ms |
4444 KB |
Output is correct |
4 |
Correct |
1 ms |
4444 KB |
Output is correct |
5 |
Correct |
2 ms |
4440 KB |
Output is correct |
6 |
Correct |
1 ms |
4444 KB |
Output is correct |
7 |
Correct |
1 ms |
4444 KB |
Output is correct |
8 |
Correct |
1 ms |
4440 KB |
Output is correct |
9 |
Correct |
1 ms |
4440 KB |
Output is correct |
10 |
Correct |
1 ms |
4444 KB |
Output is correct |
11 |
Correct |
1 ms |
4440 KB |
Output is correct |
12 |
Correct |
1 ms |
4444 KB |
Output is correct |
13 |
Correct |
1 ms |
4444 KB |
Output is correct |
14 |
Correct |
1 ms |
4444 KB |
Output is correct |
15 |
Correct |
1 ms |
4444 KB |
Output is correct |
16 |
Correct |
20 ms |
4956 KB |
Output is correct |
17 |
Correct |
19 ms |
4956 KB |
Output is correct |
18 |
Correct |
10 ms |
4956 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
1 ms |
4444 KB |
Output is correct |
3 |
Correct |
1 ms |
4444 KB |
Output is correct |
4 |
Correct |
1 ms |
4444 KB |
Output is correct |
5 |
Correct |
1 ms |
4444 KB |
Output is correct |
6 |
Correct |
1 ms |
4440 KB |
Output is correct |
7 |
Correct |
1 ms |
4444 KB |
Output is correct |
8 |
Correct |
1 ms |
4444 KB |
Output is correct |
9 |
Correct |
2 ms |
4444 KB |
Output is correct |
10 |
Correct |
1447 ms |
22020 KB |
Output is correct |
11 |
Correct |
625 ms |
21508 KB |
Output is correct |
12 |
Correct |
343 ms |
8788 KB |
Output is correct |
13 |
Correct |
2934 ms |
19388 KB |
Output is correct |
14 |
Correct |
2233 ms |
21564 KB |
Output is correct |
15 |
Correct |
1 ms |
4440 KB |
Output is correct |
16 |
Correct |
1 ms |
4444 KB |
Output is correct |
17 |
Correct |
1 ms |
4444 KB |
Output is correct |
18 |
Correct |
1 ms |
4444 KB |
Output is correct |
19 |
Correct |
1 ms |
4444 KB |
Output is correct |
20 |
Correct |
1 ms |
4444 KB |
Output is correct |
21 |
Correct |
21 ms |
4956 KB |
Output is correct |
22 |
Correct |
948 ms |
21388 KB |
Output is correct |
23 |
Correct |
737 ms |
21312 KB |
Output is correct |
24 |
Correct |
1761 ms |
25052 KB |
Output is correct |
25 |
Correct |
1835 ms |
24932 KB |
Output is correct |
26 |
Correct |
1735 ms |
22764 KB |
Output is correct |
27 |
Execution timed out |
3039 ms |
24532 KB |
Time limit exceeded |
28 |
Halted |
0 ms |
0 KB |
- |