Submission #802169

#TimeUsernameProblemLanguageResultExecution timeMemory
802169lollipopCounting Mushrooms (IOI20_mushrooms)C++17
56.93 / 100
10 ms612 KiB
#include<bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <ext/rope> #define ll 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 = 2e5 + 10 ; //mt19937 R(time(0)); int myrandom (int i) { return std::rand()%i;} map < int , int > ma , ma1 ; #include "mushrooms.h" // int use_machine(std::vector<int> x){ // } int count_mushrooms(int n){ std::srand ( unsigned ( std::time(0) ) ); vector < int > a , b ; a.pb( 0 ) ; int st ; vector < int > vv ; for( int j = 1 ; j < n ; j ++ ) vv.pb( j ) ; random_shuffle( vv.begin() , vv.end() , myrandom) ; // random_shuffle( vv.begin() , vv.end() ) ; int vs = vv.size() ; for( int k = 0 ; k < min( vs , 200 ) ; k ++ ){ vector < int > v ; int i = vv[ k ] ; v.pb( 0 ) ; v.pb( i ); int x = use_machine( v ) ; if( x == 0 ) a.pb( i ) ; else b.pb( i ) ; if( a.size() >= 100 || b.size() >= 100 ){ st = k + 1 ; break ; } } if( a.size() + b.size() == n ) return a.size() ; int tt = 0 ; if( a.size() < 100 ){ tt = 1 ; swap( a , b ) ; } for( int j = st ; j < vv.size() ; j ++ ){ int lf = vv.size() - j ; int jj = j ; vector < int > v ; int nw = 0 , cc = 0 ; if( lf >= 100 ){ FOR( i , 100 ){ v.pb( a[ i ] ) ; nw ++ ; v.pb( vv[jj] ) ; jj ++ ; } } else{ FOR( i , lf ){ v.pb( a[ i ] ) ; nw ++ ; v.pb( vv[jj] ) ; jj ++ ; } } int x = use_machine( v ) ; while( x > 0 ){ b.pb( -1 ) ; cc ++ ; x -= 2 ; } cc = nw - cc ; while( cc -- ) a.pb( -1 ) ; j = jj - 1 ; } if( tt == 0 ) return a.size() ; else return n - a.size() ; } //int use_machine(std::vector<int> x)

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:62:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   62 |     if( a.size() + b.size() == n ) return a.size() ;
      |         ~~~~~~~~~~~~~~~~~~~~^~~~
mushrooms.cpp:68:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for( int j = st ; j < vv.size() ; j ++ ){
      |                       ~~^~~~~~~~~~~
mushrooms.cpp:68:23: warning: 'st' may be used uninitialized in this function [-Wmaybe-uninitialized]
   68 |     for( int j = st ; j < vv.size() ; j ++ ){
      |                       ^
#Verdict Execution timeMemoryGrader output
Fetching results...