| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 582862 | MohamedFaresNebili | 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"
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using pi = pair<ll, pair<ll, ll>>;
using ii = pair<int, int>;
#define pb push_back
#define pp pop_back
#define ff first
#define ss second
#define lb lower_bound
typedef tree<int, null_type, less<int>, rb_tree_tag,
tree_order_statistics_node_update> indexed_set;
bool cmp(ii A, ii B) {
if(max(A.ff, A.ss) != max(B.ff, B.ss))
return max(A.ff, A.ss) > max(B.ff, B.ss);
return min(A.ff, A.ss) > min(B.ff, B.ss);
}
int putaway(int A, int B, int T, int X[],
int Y[], int W[], int S[]) {
vector<ii> arr;
for(int l = 0; l < T; l++)
arr.pb({W[l], S[l]});
sort(arr.begin(), arr.end(), cmp);
sort(X, X + A), sort(Y, Y + B);
for(int l = T - 1; l >= 0; l--) {
int U = arr[l].ff, V = arr[l].ss;
if(A > 0 && U < X[A - 1]) continue;
if(B > 0 && V < Y[B - 1]) continue;
return -1;
}
int occ[A + B];
memset(occ, 0, sizeof occ);
for(int l = 0; l < T; l++) {
int U = arr[l].ff, V = arr[l].ss;
int i = lb(X, X + A, U + 1) - X;
int j = lb(Y, Y + B, V + 1) - Y;
int L = i, R = A + j;
for(; i < A; i++)
if(occ[i] < occ[L])
L = i;
for(; j < B; j++)
if(occ[j + A] < occ[R])
R = j + A;
if(L == A) {
occ[R]++; continue;
}
if(R == A + B) {
occ[L]++; continue;
}
if(occ[R] < occ[L]) swap(L, R);
if(occ[L] == occ[R] && V > U)
swap(L, R);
occ[L]++;
}
int res = 0;
for(int l = 0; l < A + B; l++)
res = max(res, occ[l]);
return res;
}