Submission #582859

#	Time	Username	Problem	Language	Result	Execution time	Memory
582859		MohamedFaresNebili	Robots (IOI13_robots)	C++14	39 / 100	3065 ms	19572 KiB

robots

#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);
                occ[L]++;
            }
            int res = 0;
            for(int l = 0; l < A + B; l++)
                res = max(res, occ[l]);
            return res;
        }

• Subtask 1: 14 / 14
• Subtask 2: 0 / 14
• Subtask 3: 25 / 25
• Subtask 4: 0 / 37
• Subtask 5: 0 / 10