# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
965675 |
2024-04-19T04:41:18 Z |
Amr |
Robots (IOI13_robots) |
C++17 |
|
0 ms |
0 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;
n*n1*log*log
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(xx,xx+n1);
sort(yy,yy+n2);
if(good(n)==0) return -1;
ll l = 0, r = 1;
while(!good(r)) r*=2;
log*
while(l+1<r)
{
ll mid = (l+r)/2;
if(good(mid)) r = mid;
else l = mid;
}
return r;
}
Compilation message
robots.cpp: In function 'bool good(ll)':
robots.cpp:26:9: error: invalid operands of types 'll' {aka 'long long int'} and '<unresolved overloaded function type>' to binary 'operator*'
26 | n*n1*log*log
| ~~~~^~~~
robots.cpp:27:20: error: 'i' was not declared in this scope
27 | for(int i = 0; i < n1; i++)
| ^
robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:63:5: error: expected primary-expression before 'while'
63 | while(l+1<r)
| ^~~~~
robots.cpp:60:8: warning: unused variable 'l' [-Wunused-variable]
60 | ll l = 0, r = 1;
| ^