제출 #729646

#제출 시각아이디문제언어결과실행 시간메모리
729646Blistering_Barnacles로봇 (IOI13_robots)C++11
76 / 100
543 ms65536 KiB
#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(se.begin()) ; m-- ; dp[op.S] = 1 ; cur-- ; } } 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(se.begin()) ; 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 ; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...