oj.uz

Submission #296025

# Submission time Handle Problem Language Result Execution time Memory
296025 2020-09-10T08:00:39 Z Badrangiikh Gondola (IOI14_gondola) C++14
100 / 100
 52 ms 2680 KB 
#include "gondola.h"
#include<bits/stdc++.h>
using namespace std;

int valid(int n, int inputSeq[])
{
  vector < pair < int , int > > vec ;
    vector < int > vc ;
    for ( int i = 0 ; i < n ; i ++ ) {
        if ( inputSeq [ i ] <= n ) {
            vec . push_back ( { inputSeq [ i ] , i } ) ;
        }
        vc . push_back ( inputSeq [ i ] ) ;
    }
    sort ( vc . begin ( ) , vc . end ( ) ) ;
    for ( int i = 1 ; i < vc . size ( ) ; i ++ ) {
        if ( vc [ i - 1 ] == vc [ i ] ) return 0 ;
    }
    sort ( vec . begin ( ) , vec . end ( ) ) ;
    for ( int i = 1 ; i < vec . size ( ) ; i ++ ) {
        if ( vec [ i ] . first - vec [ i - 1 ] . first != ( ( vec [ i ] . second - vec [ i - 1 ] . second ) % n + n ) % n ) {
            return 0 ;
        }
    }
    return 1 ; 
}

//----------------------

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
  int maxx , minn , indx , x ;
    vector < int > vec ; 
    vector < pair < int , int > > vc ; 
    minn = n + 1 ;
    for ( int i = 0 ; i < n ; i ++ ) {
        if ( minn > gondolaSeq [ i ] ) {
            indx = i ;
            minn = gondolaSeq [ i ] ;
        }
        maxx = max ( maxx , gondolaSeq [ i ] ) ;
    }
    if ( minn <= n ) {
        for ( int i = ( n + indx - minn ) % n + 1 ; i <= ( n + indx - minn ) % n + n ; i ++ ) {
            vc . push_back ( { gondolaSeq [ i % n ] , i - ( ( n + indx - minn ) % n + 1 ) } ) ;
        }
    }
    else {
        for ( int i = 0 ; i < n ; i ++ ) {
            vc . push_back ( { gondolaSeq [ i ] , i } ) ;
        }
    }
    sort ( vc . begin ( ) , vc . end ( ) ) ;
    x = n + 1 ;
    for ( int i = 0 ; i < vc . size ( ) ; i ++ ) {
        if ( vc [ i ] . first == vc [ i ] . second + 1 ) continue ;
        vec . push_back ( vc [ i ] . second + 1 ) ;
        for ( int j = x ; j <= vc [ i ] . first - 1 ; j ++ ) {
            vec . push_back ( j ) ;
        }
        x = vc [ i ] . first + 1 ;
    } 
    for ( int i = 0 ; i < vec . size ( ) ; i ++ ) {
        replacementSeq [ i ] = vec [ i ] ;
    }
    return maxx - n ;
}

//----------------------

long long zeregt ( int s1 , int s2 ) {
    long long zer [ 45 ] ;
  long long mod1 = 1e9+9 ;
    zer [ 0 ] = s1 ;
    for ( int i = 1 ; i <= 30 ; i ++ ) {
        zer [ i ] = zer [ i - 1 ] * zer [ i - 1 ] ;
        zer [ i ] %= mod1 ;
    }
    long long s3 = 1 ;
    for ( int i = 0 ; i <= 30 ; i ++ ) {
        if ( s2 % 2 == 1 ) {
            s3 *= zer [ i ] ;
            s3 %= mod1 ;
        }
        s2 /= 2 ;
    }
    return s3 ;
}

int countReplacement(int n, int inputSeq[])
{
	long long ans , mod ;
  int x , y , z , maxx , minn , indx ;
  vector < int > ch , vec , vc ;
  vector < pair < int , int > > hc ; 
	if ( valid( n , inputSeq ) == 0 ) return 0 ;
    for ( int i = 0 ; i < n ; i ++ ) {
        vc . push_back ( inputSeq [ i ] ) ;
    }
    sort ( vc . begin ( ) , vc . end ( ) ) ;
    mod = 1000000009 ;
    ans = 1 ;
    x = n ;
    for ( int i = 0 ; i < n ; i ++ ) {
        if ( vc [ i ] <= n ) {
            continue ;
        }
        y = n - i ;
        z = vc [ i ] - x - 1 ;
        ans *= ( zeregt ( y , z ) % mod ) ;
        ans %= mod ;
        x = vc [ i ] ;
    }
    if ( vc [ 0 ] > n ) {
    	ans *= n ;
    	ans %= mod ;
	}
    return ans ;
}

Compilation message

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:16:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for ( int i = 1 ; i < vc . size ( ) ; i ++ ) {
      |                       ~~^~~~~~~~~~~~~~~
gondola.cpp:20:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for ( int i = 1 ; i < vec . size ( ) ; i ++ ) {
      |                       ~~^~~~~~~~~~~~~~~~
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:55:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for ( int i = 0 ; i < vc . size ( ) ; i ++ ) {
      |                       ~~^~~~~~~~~~~~~~~
gondola.cpp:63:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for ( int i = 0 ; i < vec . size ( ) ; i ++ ) {
      |                       ~~^~~~~~~~~~~~~~~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:93:19: warning: unused variable 'maxx' [-Wunused-variable]
   93 |   int x , y , z , maxx , minn , indx ;
      |                   ^~~~
gondola.cpp:93:26: warning: unused variable 'minn' [-Wunused-variable]
   93 |   int x , y , z , maxx , minn , indx ;
      |                          ^~~~
gondola.cpp:93:33: warning: unused variable 'indx' [-Wunused-variable]
   93 |   int x , y , z , maxx , minn , indx ;
      |                                 ^~~~
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:44:27: warning: 'indx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   44 |         for ( int i = ( n + indx - minn ) % n + 1 ; i <= ( n + indx - minn ) % n + n ; i ++ ) {
      |                         ~~^~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 256 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 308 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 11 ms 1404 KB Output is correct
7 Correct 21 ms 2680 KB Output is correct
8 Correct 18 ms 2552 KB Output is correct
9 Correct 8 ms 896 KB Output is correct
10 Correct 26 ms 2680 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 11 ms 1404 KB Output is correct
7 Correct 20 ms 2680 KB Output is correct
8 Correct 18 ms 2552 KB Output is correct
9 Correct 8 ms 896 KB Output is correct
10 Correct 26 ms 2680 KB Output is correct
11 Correct 1 ms 256 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 9 ms 1152 KB Output is correct
14 Correct 0 ms 256 KB Output is correct
15 Correct 26 ms 2296 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 256 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 288 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 288 KB Output is correct
6 Correct 0 ms 256 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 15 ms 2296 KB Output is correct
12 Correct 16 ms 2296 KB Output is correct
13 Correct 18 ms 1656 KB Output is correct
14 Correct 13 ms 2296 KB Output is correct
15 Correct 27 ms 2392 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 2 ms 256 KB Output is correct

Subtask #8
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 36 ms 2008 KB Output is correct
10 Correct 27 ms 1532 KB Output is correct
11 Correct 11 ms 808 KB Output is correct
12 Correct 14 ms 896 KB Output is correct
13 Correct 4 ms 512 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 35 ms 1880 KB Output is correct
10 Correct 27 ms 1532 KB Output is correct
11 Correct 11 ms 808 KB Output is correct
12 Correct 14 ms 896 KB Output is correct
13 Correct 4 ms 512 KB Output is correct
14 Correct 43 ms 2344 KB Output is correct
15 Correct 52 ms 2428 KB Output is correct
16 Correct 10 ms 824 KB Output is correct
17 Correct 34 ms 1656 KB Output is correct
18 Correct 19 ms 1264 KB Output is correct