Submission #779098

#	Time	Username	Problem	Language	Result	Execution time	Memory
779098		lollipop	Robots (IOI13_robots)	C++17	100 / 100	1525 ms	28972 KiB

robots

#include "robots.h"
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
//#define int long long
#define pb push_back
#define s second
#define f first
#define pf push_front
#define inf 100000000000000000
#define bitebi __builtin_popcountll
#define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
#define YES cout <<"YES\n"
#define NO cout << "NO\n"
#define debug cout << "Here Fine" << endl ;
#define pr pair < int , int >
#define fbo find_by_order // returns iterator
#define ook order_of_key // returns strictly less numbers than key
using namespace std ;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
const double Pi=acos(-1.0);
const double EPS=1E-8;
const int mod =  1000000007 ;
const int mod1 = 998244353 ;
const int NN = 2e6 + 10 ;
mt19937 R(time(0));
map < int , int > ma , ma1 ;
int been[ NN ] ; 
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]){
	int a = 0 , b = 0 ;
	FOR( i , A ) a = max( a , X[ i ] ) ;
	FOR( i , B ) b = max( b , Y[ i ] ) ;
    int aa = 0 , bb = 0 ;
	FOR( i , T ){
		aa = max( aa , W[ i ] ) ;
		bb = max( bb , S[ i ] ) ;
	} 
	int tt = 0 ; 
	FOR( i , T ){
		if( W[ i ] >= a && S[ i ] >= b ) tt = -1 ; 
	}
	if( tt == -1 ) return -1 ;
	if( B == 0 ) FOR( i , T ) S[ i ] = INT_MAX ;
	vector < pair < int , int > > v ;
	FOR( i , T ) v.pb( { W[ i ] , S[ i ] } ) ;
	sort( v.begin() , v.end() ) ; 	
	sort( X , X + A ) ;
	sort( Y , Y + B ) ;
	int l = 1 , r = T , ans ; 
	priority_queue < pair < int , int > > qu ; 
	while( l <= r ){
		while( true ){
			if( qu.size() == 0 ) break ;
			qu.pop() ;
		}
		int i = ( l + r ) / 2 ; 
		int cc = 0 ; 
		if( i == 0 ) continue ;
		int poss = 0 ; 
		FOR( i , T ) been[ i ] = 0 ;
		FOR( l , A ){
		   int x = X[ l ] ;
           int cnt = i ; 
           while( true ){
           	  if( poss == T ) break ; 
           	  if( v[ poss ].f >= x ) break ;
           	  qu.push( { v[ poss ].s , poss } );
           	  poss ++ ; 
		   }
		   while( cnt -- ){
		   	 if( qu.size() == 0 ) break ; 
		   	 pair < int , int > mx ;
		   	 mx = qu.top() ;
		   	 qu.pop() ;
			 been[ mx.s ] = 1 ;
			 cc ++ ; 
		   }	
		}
		vector < int > K ; 
		FOR( j , T ){
			if( been[ j ] == 1 ) continue ;
			K.pb( v[ j ].s ) ; 
		}
		sort( K.begin() , K.end() ) ;
		int pos = K.size() - 1 ; 
		for( int j = B - 1 ; j >= 0 ; j -- ){
			int x = Y[ j ] ;
			int cnt = i ;
			while( cnt -- ){
				if( pos == -1 ) break ; 
				if( K[ pos ] < x ){
					cc ++ ; 
					pos -- ; 
				}
				else break ; 
			}
		}
		if( cc == T ){
			ans = i ; 
			r = i - 1 ;
		} 
		else l = i + 1 ; 
	}
	return ans ;
	
}
 
 
//#define MAX_A 50000
//#define MAX_B 50000
//#define MAX_T 500000
//
//static int X[MAX_A];
//static int Y[MAX_B];
//static int W[MAX_T];
//static int S[MAX_T];
//
//int main() {
//    int A, B, T, i;
//
//	assert(scanf("%d", &A) == 1);
//	assert(scanf("%d", &B) == 1);
//	assert(scanf("%d", &T) == 1);
//
//	for (i = 0; i < A; i++)
//		assert(scanf("%d", &X[i]) == 1);
//	for (i = 0; i < B; i++)
//        assert(scanf("%d", &Y[i]) == 1);
//	for (i = 0; i < T; i++)
//        assert(scanf("%d%d", &W[i], &S[i]) == 2);
//
//	int answer = putaway(A, B, T, X, Y, W, S);
//
//	printf("%d\n", answer);
//
//	return 0;
//}

Compilation message (stderr)

robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:54:22: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   54 |  int l = 1 , r = T , ans ;
      |                      ^~~

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