# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
965684 |
2024-04-19T04:50:41 Z |
Amr |
Robots (IOI13_robots) |
C++17 |
|
3000 ms |
30488 KB |
#include "robots.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define sz size()
#define all(x) (x).begin(),(x).end()
const int N = 1e6+2;
vector<pair<ll,ll> > v;
ll n1, n2 , n;
ll xx[N],yy[N];
bool cmp(pair<ll,ll> a, pair<ll,ll> b)
{
return a.S > b.S;
}
bool cmp2(pair<ll,ll> a, pair<ll,ll> b)
{
return a.S < b.S;
}
bool good(ll x)
{
if(n2>0)sort(all(v));
ll lst = 0;
for(int i = 0; i < n1; i++)
{
pair<ll,ll> p = {xx[i],0};
ll pos = (lower_bound(v.begin(),v.end(),p)-v.begin());
pos--;
if(pos<lst) continue;
//reverse(v.begin()+lst,v.begin()+pos+1);
if(n2>0) sort(v.begin()+lst,v.begin()+pos+1,cmp);
lst = max(lst,min(pos+1,lst+x));
//if(lst!=pos+1) sort(v.begin()+lst,v.begin()+pos+1);
// cout << pos << " ";
}
if(lst!=n&&n2>0)
sort(v.begin()+lst,v.begin()+n,cmp2);
for(int i = 0; i < n2; i++)
{
ll cnt = 0;
while(cnt<x&&lst<n&&v[lst].S<yy[i]) cnt++,lst++;
}
return (lst==n);
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
n = T , n1 = A , n2 = B;
v.resize(n);
for(int i = 0; i < A; i++) xx[i] = X[i];
for(int i = 0; i < B; i++) yy[i] = Y[i];
for(int i = 0; i < n; i++) v[i] = {W[i],S[i]};
sort(all(v));
sort(xx,xx+n1);
sort(yy,yy+n2);
if(good(n)==0) return -1;
ll l = 0, r = n;
//while(!good(r)) r*=2;
while(l+1<r)
{
ll mid = (l+r)/2;
if(good(mid)) r = mid;
else l = mid;
}
return r;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
8536 KB |
Output is correct |
2 |
Correct |
1 ms |
6492 KB |
Output is correct |
3 |
Correct |
1 ms |
6492 KB |
Output is correct |
4 |
Correct |
1 ms |
8652 KB |
Output is correct |
5 |
Correct |
1 ms |
6600 KB |
Output is correct |
6 |
Correct |
1 ms |
6492 KB |
Output is correct |
7 |
Correct |
1 ms |
6492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6492 KB |
Output is correct |
2 |
Correct |
1 ms |
6492 KB |
Output is correct |
3 |
Correct |
1 ms |
6492 KB |
Output is correct |
4 |
Correct |
190 ms |
18696 KB |
Output is correct |
5 |
Correct |
131 ms |
29008 KB |
Output is correct |
6 |
Correct |
61 ms |
12632 KB |
Output is correct |
7 |
Correct |
199 ms |
27160 KB |
Output is correct |
8 |
Correct |
182 ms |
29436 KB |
Output is correct |
9 |
Correct |
148 ms |
29136 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
8540 KB |
Output is correct |
2 |
Correct |
1 ms |
8540 KB |
Output is correct |
3 |
Correct |
1 ms |
8540 KB |
Output is correct |
4 |
Correct |
1 ms |
6492 KB |
Output is correct |
5 |
Correct |
1 ms |
6492 KB |
Output is correct |
6 |
Correct |
1 ms |
8540 KB |
Output is correct |
7 |
Correct |
1 ms |
6492 KB |
Output is correct |
8 |
Correct |
1 ms |
6492 KB |
Output is correct |
9 |
Correct |
1 ms |
6492 KB |
Output is correct |
10 |
Correct |
1 ms |
8540 KB |
Output is correct |
11 |
Correct |
1 ms |
8536 KB |
Output is correct |
12 |
Correct |
1 ms |
8540 KB |
Output is correct |
13 |
Correct |
1 ms |
8540 KB |
Output is correct |
14 |
Correct |
1 ms |
8540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
8540 KB |
Output is correct |
2 |
Correct |
1 ms |
8540 KB |
Output is correct |
3 |
Correct |
1 ms |
8540 KB |
Output is correct |
4 |
Correct |
1 ms |
6488 KB |
Output is correct |
5 |
Correct |
1 ms |
6492 KB |
Output is correct |
6 |
Correct |
1 ms |
8540 KB |
Output is correct |
7 |
Correct |
1 ms |
6492 KB |
Output is correct |
8 |
Correct |
1 ms |
6600 KB |
Output is correct |
9 |
Correct |
1 ms |
6492 KB |
Output is correct |
10 |
Correct |
1 ms |
8540 KB |
Output is correct |
11 |
Correct |
1 ms |
8540 KB |
Output is correct |
12 |
Correct |
1 ms |
8540 KB |
Output is correct |
13 |
Correct |
1 ms |
8540 KB |
Output is correct |
14 |
Correct |
1 ms |
8540 KB |
Output is correct |
15 |
Correct |
1 ms |
8540 KB |
Output is correct |
16 |
Correct |
315 ms |
8840 KB |
Output is correct |
17 |
Correct |
233 ms |
8796 KB |
Output is correct |
18 |
Correct |
650 ms |
8836 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
8540 KB |
Output is correct |
2 |
Correct |
2 ms |
8540 KB |
Output is correct |
3 |
Correct |
2 ms |
8536 KB |
Output is correct |
4 |
Correct |
1 ms |
6488 KB |
Output is correct |
5 |
Correct |
1 ms |
6492 KB |
Output is correct |
6 |
Correct |
1 ms |
8540 KB |
Output is correct |
7 |
Correct |
1 ms |
6492 KB |
Output is correct |
8 |
Correct |
1 ms |
6492 KB |
Output is correct |
9 |
Correct |
1 ms |
6492 KB |
Output is correct |
10 |
Correct |
195 ms |
18524 KB |
Output is correct |
11 |
Correct |
127 ms |
29008 KB |
Output is correct |
12 |
Correct |
60 ms |
12636 KB |
Output is correct |
13 |
Correct |
204 ms |
27160 KB |
Output is correct |
14 |
Correct |
183 ms |
29436 KB |
Output is correct |
15 |
Correct |
1 ms |
8536 KB |
Output is correct |
16 |
Correct |
1 ms |
8540 KB |
Output is correct |
17 |
Correct |
1 ms |
8540 KB |
Output is correct |
18 |
Correct |
1 ms |
8540 KB |
Output is correct |
19 |
Correct |
1 ms |
8644 KB |
Output is correct |
20 |
Correct |
1 ms |
8540 KB |
Output is correct |
21 |
Correct |
312 ms |
9056 KB |
Output is correct |
22 |
Correct |
1843 ms |
25028 KB |
Output is correct |
23 |
Correct |
155 ms |
29008 KB |
Output is correct |
24 |
Correct |
602 ms |
30168 KB |
Output is correct |
25 |
Correct |
595 ms |
30092 KB |
Output is correct |
26 |
Correct |
533 ms |
30488 KB |
Output is correct |
27 |
Execution timed out |
3023 ms |
29772 KB |
Time limit exceeded |
28 |
Halted |
0 ms |
0 KB |
- |