Submission #729938

#	Time	Username	Problem	Language	Result	Execution time	Memory
729938		Rasoul006	Robots (IOI13_robots)	C++17	14 / 100	3062 ms	65536 KiB

robots

#include "robots.h"
 
#include <bits/stdc++.h>
 
#define endl "\n"
 
#define F first
 
#define S second
 
#define pb push_back
 
#define all(x) x.begin() , x.end()
 
#define mm(dp , val) memset (dp , val , sizeof dp)
 
#define mid ((r+l)>>1)
 
#define lx (n<<1)
 
#define rx ((n<<1)|1)
 
typedef long long ll;
 
using namespace std;
 
const int logn = 26 ;
 
const int N = 1e6+5;
 
ll n , m , q , x[N] , y[N] , s[N] , w[N] ;
 
multiset <pair<ll , ll>> st1 , st2 ;
 
vector <pair <ll , bool>> vec ;
 
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
 
    n = A , m = B , q = T ;
 
    for (int i = 0 ; i<n ; i++)
    {
        x[i] = X[i] ;
        vec.pb({x[i] , 0}) ;
    }
 
    for (int i = 0 ; i<m ; i++)
    {
        y[i] = Y[i] ;
        vec.pb({y[i] , 1}) ;
    }
 
    for (int i = 0 ; i<q ; i++)
    {
        w[i] = W[i] , s[i] = S[i] ;
        st1.insert({w[i] , s[i]}) ;
        st2.insert({s[i] , w[i]}) ;
    }
 
    sort (all(vec)) ;
    
    sort (y , y+m) ;
    sort (x , x+n) ;
    
    for (int i = 0 ; i<q ; i++)
    {
        if (w[i] < x[n-1] || s[i] < y[m-1]) continue ;
        return -1 ;
    }
 
//    for (auto it : vec)
//        cout << "(" << it.F << ", " << it.S << ") " ;
//    cout << endl ;
 
    ll ans = 0 ;
 
    while (!st1.empty())
    {
//
//        for (auto it : st1)
//            cout << it.F << " " ;
//        cout << endl ;
//
//        for (auto it : st1)
//            cout << it.S << " " ;
//        cout << endl ;
 
        for (auto i : vec)
        {
            ll x = i.F ; bool ty = i.S ;
 
            if (ty)
            {
                auto it = st2.lower_bound({x , 0}) ;
 
                pair <ll,ll> pr = *it ;
 
                if (it == st2.begin() && pr.F >= x)
                    continue ;
 
                if (st2.begin() != it)
                    it--;
 
                pr = *it ;
 
                st2.erase(it) ;
                st1.erase(st1.find({pr.S , pr.F})) ;
 
//                cout << x << " " << pr.F << endl ;
            }
 
            else
            {
                auto it = st1.lower_bound({x , 0}) ;
 
                pair <ll,ll> pr = *it ;
                if (it == st1.begin() && pr.F >= x)
                    continue ;
 
                if (it != st1.begin())
                    it--;
                pr = *it ;
                st1.erase(it) ;
                st2.erase(st2.find({pr.S , pr.F})) ;
 
//                cout << x << " " << pr.F << endl ;
            }
        }
 
        ans++;
    }
 
    return ans ;
}

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