#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 ){
set<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;
| ~~^~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4440 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 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
4444 KB |
Output is correct |
2 |
Incorrect |
2 ms |
4444 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
1 ms |
4536 KB |
Output is correct |
3 |
Correct |
1 ms |
4536 KB |
Output is correct |
4 |
Correct |
1 ms |
4440 KB |
Output is correct |
5 |
Correct |
1 ms |
4440 KB |
Output is correct |
6 |
Correct |
1 ms |
4440 KB |
Output is correct |
7 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4440 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 |
4536 KB |
Output is correct |
5 |
Correct |
1 ms |
4444 KB |
Output is correct |
6 |
Correct |
1 ms |
4444 KB |
Output is correct |
7 |
Incorrect |
1 ms |
4536 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
1 ms |
4444 KB |
Output is correct |
3 |
Correct |
1 ms |
4536 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 |
4696 KB |
Output is correct |
7 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |