#include "gondola.h"
#include <bits/stdc++.h>
using namespace std ;
typedef pair<int,int> pii ;
int arr[300000] ;
const int MOD = 1e9+9 ;
int valid(int n, int inputSeq[])
{
int x = min_element ( inputSeq, inputSeq+n ) - inputSeq ;
vector <int> nwSeq ;
set <int> rep ;
for ( int i = x ; i < n ; ++i ) nwSeq.push_back ( inputSeq[i] ), rep.insert ( inputSeq[i] ) ;
for ( int i = 0 ; i < x ; ++i ) nwSeq.push_back ( inputSeq[i] ), rep.insert ( inputSeq[i] ) ;
int expected = inputSeq[x] ;
int posible = ( (int)rep.size()==n ) ;
for ( int i = 0 ; i < n ; ++i ) {
if ( nwSeq[i] <= n ) {
if ( nwSeq[i] != expected ) posible = 0 ;
expected = nwSeq[i]+1 ;
}
else expected++ ;
}
return posible;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int x = min_element ( gondolaSeq, gondolaSeq+n ) - gondolaSeq ;
int beg = 1 ;
if ( gondolaSeq[x] <= n ) beg = gondolaSeq[x] ;
if ( *max_element(gondolaSeq, gondolaSeq+n) > n ) return 1 ;
vector <int> nwSeq ;
for ( int i = x ; i < n ; ++i ) nwSeq.push_back ( gondolaSeq[i] ) ;
for ( int i = 0 ; i < x ; ++i ) nwSeq.push_back ( gondolaSeq[i] ) ;
// cout << beg << '\n' ;
vector <pii> posib ;
for ( int i = 0 ; i < n ; ++i ) {
if ( nwSeq[i] != beg ) posib.push_back ( {nwSeq[i], beg} ) ;
beg++ ;
if ( beg > n ) beg = 1;
}
sort ( posib.begin(), posib.end() ) ;
int ans = 0, id = 0;
for ( auto i:posib ) {
// cout << i.first << ' ' << i.second << '\n' ;
replacementSeq[id] = i.second ;
n++ ;
++ans ;
while ( n < i.first ) {
++id ;
replacementSeq[id] = n ;
++n ;
++ans ;
}
++id ;
}
return ans;
}
long long fpow( long long q, long long cur ) {
if ( cur == 1 ) return q ;
if ( cur == 0 ) return 1 ;
long long izq = fpow(q, cur/2) ;
long long ot = max(1ll,(cur%2)*q) ;
return (((izq*izq)%MOD)*ot)%MOD ;
}
//----------------------
int countReplacement(int n, int inputSeq[])
{
if ( valid(n, inputSeq) == 0 ) return 0 ;
if ( replacement (n,inputSeq,arr) == 0 ) return 1 ;
sort ( inputSeq, inputSeq + n ) ;
long long ans = 1 ;
if ( inputSeq[0] > n ) ans = n ;
int nRep = n ;
for ( int i = 0 ; i < nRep ; ++i ) {
long long cur = inputSeq[i] - n ;
if ( cur <= 0 ) continue ;
cur-- ;
long long q = nRep-i ;
n = inputSeq[i] ;
ans *= (fpow(q,cur)%MOD) ;
ans %= MOD;
}
return ans ;
}
/*
10
10
1 2 5644898 4 8489426 6 898894 8 948945 8946521*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
3 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
3 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
276 KB |
Output is correct |
2 |
Correct |
4 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
4 ms |
376 KB |
Output is correct |
6 |
Correct |
21 ms |
2416 KB |
Output is correct |
7 |
Correct |
40 ms |
3952 KB |
Output is correct |
8 |
Correct |
31 ms |
4212 KB |
Output is correct |
9 |
Correct |
10 ms |
1528 KB |
Output is correct |
10 |
Correct |
40 ms |
4848 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
256 KB |
Output is correct |
4 |
Correct |
2 ms |
252 KB |
Output is correct |
5 |
Correct |
1 ms |
376 KB |
Output is correct |
6 |
Correct |
16 ms |
2420 KB |
Output is correct |
7 |
Correct |
42 ms |
4080 KB |
Output is correct |
8 |
Correct |
32 ms |
4212 KB |
Output is correct |
9 |
Correct |
9 ms |
1628 KB |
Output is correct |
10 |
Correct |
37 ms |
4852 KB |
Output is correct |
11 |
Correct |
3 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
252 KB |
Output is correct |
13 |
Correct |
23 ms |
2232 KB |
Output is correct |
14 |
Correct |
2 ms |
376 KB |
Output is correct |
15 |
Correct |
65 ms |
5104 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
376 KB |
Integer 0 violates the range [1, 76] |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
376 KB |
Integer 0 violates the range [1, 76] |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
248 KB |
Integer 0 violates the range [1, 76] |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Correct |
2 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Correct |
1 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
1 ms |
248 KB |
Output is correct |
8 |
Correct |
9 ms |
504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
5 ms |
376 KB |
Output is correct |
3 |
Correct |
3 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
256 KB |
Output is correct |
8 |
Correct |
2 ms |
504 KB |
Output is correct |
9 |
Correct |
56 ms |
4848 KB |
Output is correct |
10 |
Correct |
42 ms |
4084 KB |
Output is correct |
11 |
Correct |
19 ms |
1784 KB |
Output is correct |
12 |
Correct |
19 ms |
2040 KB |
Output is correct |
13 |
Correct |
6 ms |
760 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
256 KB |
Output is correct |
4 |
Correct |
3 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
256 KB |
Output is correct |
6 |
Correct |
2 ms |
256 KB |
Output is correct |
7 |
Correct |
2 ms |
256 KB |
Output is correct |
8 |
Correct |
2 ms |
504 KB |
Output is correct |
9 |
Correct |
31 ms |
4820 KB |
Output is correct |
10 |
Correct |
45 ms |
4084 KB |
Output is correct |
11 |
Correct |
17 ms |
1656 KB |
Output is correct |
12 |
Correct |
18 ms |
2012 KB |
Output is correct |
13 |
Correct |
6 ms |
760 KB |
Output is correct |
14 |
Correct |
79 ms |
5876 KB |
Output is correct |
15 |
Correct |
86 ms |
6512 KB |
Output is correct |
16 |
Correct |
14 ms |
1556 KB |
Output is correct |
17 |
Correct |
48 ms |
4352 KB |
Output is correct |
18 |
Correct |
26 ms |
2680 KB |
Output is correct |