Submission #729649

#	Time	Username	Problem	Language	Result	Execution time	Memory
729649		Blistering_Barnacles	Robots (IOI13_robots)	C++17	76 / 100	510 ms	65536 KiB

robots

#include "robots.h"
//Billions of bilious blue blistering barnacles in a thundering typhoon!
#pragma GCC optimize("Ofast,fast-math,unroll-loops")
#pragma GCC target("avx2,fma")
#include<bits/stdc++.h>
#define fast ios::sync_with_stdio(0) , cin.tie(0)
#define F first
#define S second
#define pb push_back
#define vll vector< ll >
#define vi vector< int >
#define pll pair< ll , ll >
#define pi pair< int , int >
#define all(s) s.begin() , s.end()
#define sz(s) s.size()
#define str string
#define md ((s + e) / 2)
#define mid ((l + r) / 2)
#define msdp(dp) memset(dp , -1 , sizeof dp)
#define mscl(dp) memset(dp , 0 , sizeof dp)
#define C continue
#define R return
#define B break
#define lx node * 2
#define rx node * 2 + 1
#define br(dosomething) {dosomething; break;}
#define co(dosomething) {dosomething ; continue;}
using namespace std;
typedef long long ll;
ll q, dp[1500005] , a[1555555] , b[1555555], k, l, m, n, o, p;
map < ll , ll > mp;
vll adj[555555];
const ll mod = 1e9+7;
str s ;
pll c1[1555555] , c2[1555555] ;
pll op[1555555] ;
ll n1 , n2 ;
bool ok(ll cnt){
    for(ll i = 0 ; i < n ; i++)dp[i] = 0 ;
    set < pll > se ;
    ll j = 0 ;
    m = n ;
    for(ll i = 0 ; i < n1 ; i++){
        while(j < n){
            if(dp[c1[j].S])co(j++) ;
            if(c1[j].F >= a[i])B ;
            se.insert({-op[c1[j].S].S , c1[j].S}) ;
            j++ ;
        }
        ll cur = cnt ;
        while(cur > 0 && !se.empty()){
            pll op = *se.begin() ;
            se.erase(op) ;
            m-- ;
            dp[op.S] = 1 ;
            cur-- ;
        }
    }
    if(!m)R 1 ;
    if(!n2)R 0 ; 
    j = 0 ;
    se.clear() ;
    for(ll i = 0 ; i < n2 ; i++){
        while(j < n){
            if(dp[c2[j].S])co(j++) ;
            if(c2[j].F >= b[i])B ;
            se.insert({-op[c2[j].S].F , c2[j].S}) ;
            j++ ;
        }
        ll cur = cnt ;
        while(cur > 0 && !se.empty()){
            pll op = *se.begin() ;
            se.erase(op) ;
            m-- ;
            dp[op.S] = 1 ;
            cur-- ;
        }
    }
    R !m ;
}
int putaway(int A, int bb, int T, int X[], int Y[], int W[], int S[]) {
    n = T ;
    n1 = A , n2 = bb ;
    for(ll i = 0 ; i < T ; i++){
        c1[i] = {W[i] , i} ;
        c2[i] = {S[i] , i} ;
        op[i] = {W[i] , S[i]} ;
    }
    for(ll i = 0 ; i < A ; i++){
        a[i] = X[i] ;
    }
    for(ll i = 0 ; i < bb ; i++){
        b[i] = Y[i] ;
    }
    sort(c1 , c1 + T) ;
    sort(c2 , c2 + T) ;
    if(A)sort(a , a + A) ;
    if(bb)sort(b , b + bb) ;
    ll l = -1 , r = T + 1 ;
    while(r - l > 1){
        if(ok(mid))r = mid ;
        else l = mid ;
    }
    if(!ok(r))R -1 ;
    else R r ;
}

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