| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 294290 | Badrangiikh | Gondola (IOI14_gondola) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#include "gondola.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 ;
vector < pair < int , int > > hc , vc ;
for ( int i = 0 ; i < n ; i ++ ) {
ch . push_back ( inputSeq [ i ] ) ;
if ( inputSeq [ i ] <= n ) {
hc . push_back ( { inputSeq [ i ] , i + 1 } ) ;
}
}
sort ( ch . begin ( ) , ch . end ( ) ) ;
for ( int i = 1 ; i < ch . size ( ) ; i ++ ) {
if ( ch [ i ] == ch [ i - 1 ] ) {
return 0 ;
}
}
sort ( hc . begin ( ) , hc . end ( ) ) ;
for ( int i = 1 ; i < hc . size ( ) ; i ++ ) {
if ( hc [ i ] . first - hc [ i - 1 ] . first != ( ( hc [ i ] . second - hc [ i - 1 ] . second ) % n + n ) % n ) {
return 0 ;
}
}
minn = n + 1 ;
for ( int i = 0 ; i < n ; i ++ ) {
if ( minn > inputSeq [ i ] ) {
indx = i ;
minn = inputSeq [ i ] ;
}
maxx = max ( maxx , inputSeq [ i ] [ i ] ) ;
}
if ( minn <= n ) {
for ( int i = ( n + indx - minn ) % n + 1 ; i <= ( n + indx - minn ) % n + n ; i ++ ) {
vc . push_back ( { inputSeq [ i ] [ i % n ] , i - ( ( n + indx - minn ) % n + 1 ) } ) ;
}
}
else {
for ( int i = 0 ; i < n ; i ++ ) {
vc . push_back ( { inputSeq [ i ] , i } ) ;
}
}
sort ( vc . begin ( ) , vc . end ( ) ) ;
mod = 1000000009 ;
for ( int i = 0 ; i < n ; i ++ ) {
if ( vc [ i ] . first != i + 1 ) {
x = i + 1 ;
y = n - i ;
break ;
}
}
ans = 1 ;
for ( int i = 0 ; i < n ; i ++ ) {
if ( vc [ i ] . first == i + 1 ) {
continue ;
}
z = vc [ i ] . first - x ;
ans *= ( zeregt ( y , z ) % mod ) ;
ans %= mod ;
x = vc [ i ] . first + 1 ;
y -- ;
}
x = ans ;
return x ;
}