Submission #800166

#	Time	Username	Problem	Language	Result	Execution time	Memory
800166		lollipop	Comparing Plants (IOI20_plants)	C++17	14 / 100	4064 ms	5792 KiB

plants

#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));
map < int , int > ma , ma1 ;

#include "plants.h"

int tt = 2 ;
vector < int > v ; 
int sm[ 300000 ] ;
int case1( int x , int y ){
    int n = v.size() ;
    int cc = 0 ;
    int tt = 1 ;
    if( x > y ) tt = -1 , swap( x , y ) ;
    int ss = sm[ y - 1 ] ;
    if( x != 0 ) ss -= sm[ x - 1 ] ;
    int pas = 0 ;
    if( x == 0 && y == n - 1 ){
        if( v[ y ] == 1 ) pas = 1 ;
        else pas = -1 ;
    }
    else{
      if( ss == 0 ) pas = 1 ;
      else{
        if( ss != ( y - x ) ){
            int ss1 = sm[ v.size() - 1 ] - sm[ y - 1 ] ;
            if( x != 0 )
            ss1 = ss1 + sm[ x - 1 ] ;
            int len = v.size() - y ;
            len += x ;
            if( ss1 == 0 ){
                pas = 0 ; 
            }
            else if( ss1 == len ) pas = 1 ;
            else 
            if( len != ss1 ) pas = 0 ;
        }
        else pas = -1 ;
      }
    }
    pas *= tt ;
    return pas ;
    
    // if( x < y ){
    //     if( x == 0 && y != n - 1 && y != 1 ) return 0 ;
    //     if( x == 0 && y == n - 1 ){
    //        if( v[ y ] == 0 ) return -1 ;
    //        else return 1 ;
    //     }
    //     if( x + 1 != y ) return 0 ;
    //     if( v[ x ] == 0 ) return 1 ;
    //     else return -1 ;
    // }
    // swap( x , y ) ;
    //     if( x == 0 && y != n - 1 && y != 1 ) return 0 ;
    //     if( x == 0 && y == n - 1 ){
    //        if( v[ y ] == 0 ) return 1 ;
    //        else return -1 ;
    //     }
    //     if( x + 1 != y ) return 0 ;
    //     if( v[ x ] == 0 ) return -1 ;
    //     else return 1 ;  
}
int a[ 300000 ] ;
int been[ 300000 ] ;
int case2( int x , int y ){
    if( a[ x ] < a[ y ] )return -1 ;
    else return 1 ;

}
void init(int k, std::vector<int> r){
     tt = k ; 
     if( k == 2 ){
       FOR( i , v.size() ){
        if( i != 0 ) sm[ i ] = sm[ i - 1 ] ;
        sm[ i ] = sm[ i ] + v[ i ] ; 
       }
       v = r ; return ;
     }     
     int cnt = 0 ;
     int nn = r.size() ;
     FOR( i , nn ) been[ i ] = 0 ;
     int cur = nn - 1 ; 
     while( true ){
        if( cnt == nn - 1 ){
            FOR( i , nn ) if( been[ i ] == 0 ){
                a[ i ] = 0 ; break ;
            }
            break ; 
        }
        vector < int > v ;
        FOR( i , nn ){
            if( r[ i ] == 0 ) v.pb( i ) ; 
        }
        int x = v[ 0 ] ;
        if( v.size() != 1 ){
           pair < int , int > mx ;
           mx.f = -1 ;
           FOR( i , v.size() ){
             if( i == 0 ){
              int cur = v[ i ] + ( nn - 1 - v[ v.size() - 1 ] ) ;
              if( cur > mx.f ){
                mx = { cur , v[ i ] } ; 
              }
             }
             else{
              int cur = v[ i ] - v[ i - 1 ] - 1 ;
              if( cur > mx.f ){
                mx = { cur , v[ i ] } ; 
              }
             }
           }
           x = mx.s ; 
        }
        been[ x ] = 1 ;
        a[ x ] = cur ; 
        r[ x ] = -1 ; 
        int pos = x - 1 ;
        int kk = k - 1 ; 
        while( kk -- ){           
            if( pos < 0 ) pos = nn - 1 ;
           r[ pos ] -- ;
           pos -- ;

        }
        cnt ++ ; cur -- ;
     }
}

int compare_plants(int x, int y){
    if( tt == 2 ) return case1( x , y ) ;
    else return case2( x , y ) ;
}


// static int n, k, q;
// static std::vector<int> r;
// static std:: vector<int> x;
// static std:: vector<int> y;
// static std:: vector<int> answer;
// int main() {
// 	assert(scanf("%d%d%d", &n, &k, &q) == 3);
// 	r.resize(n);
// 	answer.resize(q);
// 	for (int i = 0; i < n; i++) {
// 		int value;
// 		assert(scanf("%d", &value) == 1);
// 		r[i] = value;
// 	}
// 	x.resize(q);
// 	y.resize(q);
// 	for (int i = 0; i < q; i++) {
// 		assert(scanf("%d%d", &x[i], &y[i]) == 2);
// 	}

// 	init(k, r);
// 	for (int i = 0; i < q; i++) {
// 		answer[i] = compare_plants(x[i], y[i]);
// 	}


// 	for (int i = 0; i < q; i++) {
// 		printf("%d\n", answer[i]);
// 	}


// 	return 0;
// }

Compilation message (stderr)

plants.cpp: In function 'int case1(int, int)':
plants.cpp:40:9: warning: unused variable 'cc' [-Wunused-variable]
   40 |     int cc = 0 ;
      |         ^~
plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:12:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
......
  102 |        FOR( i , v.size() ){
      |             ~~~~~~~~~~~~                 
plants.cpp:102:8: note: in expansion of macro 'FOR'
  102 |        FOR( i , v.size() ){
      |        ^~~
plants.cpp:12:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
......
  127 |            FOR( i , v.size() ){
      |                 ~~~~~~~~~~~~             
plants.cpp:127:12: note: in expansion of macro 'FOR'
  127 |            FOR( i , v.size() ){
      |            ^~~

• Subtask 1: 0 / 5
• Subtask 2: 14 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25