| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 483132 | MohamedAliSaidane | Robots (IOI13_robots) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
//#include "robots.h"
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> ti;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<ll> vll;
typedef pair<ld,ld> pld;
#define pb push_back
#define popb pop_back()
#define pf push_front
#define popf pop_front
#define ff first
#define ss second
#define MOD (ll)(1000000007)
#define INF (ll) (1e18)
#define all(v) (v).begin(),(v).end()
const int nx[8] = {0, 0, 1, -1,1,1,-1,-1}, ny[8] = {1, -1, 0, 0,1,-1,1,-1}; //East, West, South, North+
ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;}
ll lcm(ll a, ll b){return (a / gcd(a, b)) * b;}
////////////******SOLUTION******\\\\\\\\\\\
const int MAX_T = 1e6 + 4;
const int MAX_N = 5e4 + 4;
int A, B, T;
int X[MAX_N],Y[MAX_N], W[MAX_T], S[MAX_T];
pii toys[MAX_T];
pii byW[MAX_T];
pii byS[MAX_T];
int smax = 1;
bool comp(pii a, pii b)
{
if(a.ff == b.ff)
return a.ss >= b.ss;
else
return a.ff < b.ff;
}
bool how(pii a, pii b)
{
if(a.ss == b.ss)
return a.ff >= b.ff;
else
return a.ss < b.ss;
}
bool test(int x)
{
//cout << x << " : \n";
multiset<int> s;
int time = 0;
int j = 0;
int seen = 0;
for(int i = 0; i< A; i ++)
{
int time = 0;
for(; byW[j].ff < X[i] && j <T; j ++)
s.insert(-byW[j].ss);
while(time < x && !s.empty())
{
s.erase(s.begin());
time ++;
}
}
vi v;
for(auto e: s)
v.pb(-e);
for(;j<T;j++)
v.pb(byW[j].ss);
sort(all(v));
j = v.size()-1;
for(int i = B-1; j >= 0 && i >= 0; i --)
{
if(v[j] >= Y[i])
return 0;
j -= x;
i --;
}
return j < 0;
}
int putaway(int a, int b, int t, int x[], int y[], int w[], int s[])
{
A = a, B = b, T = t;
sort(x,x+A); sort(y,y+b);
for(int i = 0; i < A; i ++)
X[i] = x[i];
for(int i = 0; i < B; i ++)
Y[i] = y[i];
for(int i = 0; i < T; i ++)
{
W[i] = w[i];
S[i] = s[i];
byW[i] = byS[i] = toys[i] = {W[i],S[i]};
}
int wmax = 0;
for(int i = 0; i < A; i ++)
wmax = max(wmax,X[i]);
for(int i = 0; i < B; i ++)
smax = max(smax,Y[i]);
for(int i = 0; i < T; i ++)
if(W[i] >= wmax && S[i] >= smax)
return -1;
sort(byW,byW+T,comp);
if(B == 0)
{
int debut = 1;
int fin = T;
int ans = T;
sort(W,W+T);
while(debut <= fin)
{
int mid = (debut+fin)/2;
bool flag= true;
int i = A-1;
int j = T -1;
while(j >= 0)
{
if(i < 0 || W[j] >= X[i])
{
flag=false;
break;
}
j -= mid;
i--;
}
if(flag)
{
ans = mid;
fin = mid -1;
}
else
debut = mid + 1;
}
return ans;
}
//for(int i = 0; i < T; i ++)
//cout << byW[i].ff << ' ' << byW[i].ss << '\n';
//cout << '\n';
//sort(byS,byS+T,how);
int debut = 1;
int fin = T;
int ans = T;
while(debut <= fin)
{
int mid = (debut+fin)/2;
if(test(mid))
{
ans = mid;
fin = mid - 1;
}
else
debut = mid + 1;
}
return ans;
}
/*
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int A, B, T;
cin >> A >> B >> T;
int X[A], Y[B], W[T], S[T];
for(int i = 0; i < A; i ++)
{
int x; cin >> x;
X[i]=x;
}
for(int i = 0; i< B; i ++)
{
int y; cin >> y;
Y[i]=y;
}
for(int i = 0; i < T; i ++)
{
int w, s;
cin >> w >> s;
W[i] = w;
S[i] = s;
}
cout << putaway(A,B,T,X,Y,W,S) << '\n';
}
/*
5 0 6
2 3 4 5 6
1 80
2 80
3 80
4 80
1 80
5 80
*/
/*
3 2 10
6 2 9
4 7
4 6
8 5
2 3
7 9
1 8
5 1
3 3
8 7
7 6
10 5
*/