# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
965678 |
2024-04-19T04:42:39 Z |
Amr |
Robots (IOI13_robots) |
C++17 |
|
3000 ms |
18536 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)
{
//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);
//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)
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 = 1;
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 |
8540 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 |
8540 KB |
Output is correct |
5 |
Correct |
1 ms |
6492 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 |
6488 KB |
Output is correct |
3 |
Correct |
1 ms |
6492 KB |
Output is correct |
4 |
Incorrect |
251 ms |
18536 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3048 ms |
8540 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3016 ms |
8540 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3039 ms |
8540 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |