#include "gondola.h"
#include <iostream>
#include<cstdio>
#include<vector>
#include<bits/stdc++.h>
using namespace std;
long long power( int x, int e ){
long long _pos = x;
long long _s = 1;
while( e ){
int a = e % 2;
if( a == 1 ){
_s *= _pos;
_s %= 1000000009;
}
_pos *= _pos;
_pos %= 1000000009;
e /= 2;
}
return _s;
}
int valid(int n, int inputSeq[])
{
map< int, bool> m;
bool lol = 1;
int ind = -1;
for( int i = 0 ; i < n ; i++ ){
if( inputSeq[i] <= n ){
lol = 0;
ind = i;
}
if( inputSeq[i] > n ){
if( m[inputSeq[i]] == 1 ) return 0;
m[inputSeq[i]] = 1;
}
}
if( lol == 1 ){
return 1;
}
int ct[n + 5];
int nn = n + inputSeq[ind] - 1 - ind;
for( int i = 0 ; i < n ; i++ ){
ct[(nn + i) % n] = inputSeq[i];
}
for( int i = 0 ; i < n ; i++ ){
if( ct[i] <= n ){
if( i != ct[i] - 1 ){
return 0;
}
}
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int ind = -1;
int ct[n + 5];
vector< pair<int, int> >v;
for( int i = 0 ; i < n ; i++ ){
if( gondolaSeq[i] <= n ){
ind = i;
}
}
int nn = n + gondolaSeq[ind] - 1 - ind;
for( int i = 0 ; i < n ; i++ ){
ct[(nn + i) % n] = gondolaSeq[i];
}
for( int i = 0 ; i < n ; i++ ){
v.push_back( make_pair(ct[i], i));
}
sort( v.begin(), v.end());
int pos = 0;
for( int i = 0 ; i < n ; i++ ){
int ct1 = v[i].first;
if( ct1 <= n ) continue;
if( i == 0 ){
replacementSeq[pos] = v[0].second + 1;
pos++;
for( int ii = n + 1 ; ii < v[0].first ; ii++ ){
replacementSeq[pos] = ii;
pos++;
}
continue;
}
if( v[i - 1].first <= n ){
replacementSeq[pos] = v[i].second + 1;
pos++;
for( int ii = n + 1 ; ii < v[i].first ; ii++ ){
replacementSeq[pos] = ii;
pos++;
}
continue;
}
replacementSeq[pos] = v[i].second + 1;
pos++;
for( int ii = v[i-1].first + 1 ; ii < v[i].first ; ii++ ){
replacementSeq[pos] = ii;
pos++;
}
}
return pos;
}
//----------------------
int countReplacement(int n, int inputSeq[])
{
if( valid( n, inputSeq) != 1 ){
return 0;
}
vector<int> v;
bool lol = 1;
bool fuck = 1;
for( int i = 0 ; i < n ; i++ ){
if( inputSeq[i] > n ) lol = 0;
if( inputSeq[i] <= n ) fuck = 0;
v.push_back(inputSeq[i]);
}
if( lol == 1 ) return 1;
sort( v.begin(), v.end());
long long s = 1;
int pos = n + 1;
for( int i = 0 ; i < n ; i++){
if( v[i] <= n ) continue;
s *= power( n - i, v[i] - pos );
s %= 1000000009;
pos = v[i] + 1;
}
if( fuck == 1 ){
s *= (long long)n;
s %= 1000000009;
}
return s;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
416 KB |
Output is correct |
4 |
Correct |
2 ms |
492 KB |
Output is correct |
5 |
Correct |
3 ms |
512 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
560 KB |
Output is correct |
2 |
Correct |
3 ms |
560 KB |
Output is correct |
3 |
Correct |
3 ms |
560 KB |
Output is correct |
4 |
Correct |
2 ms |
560 KB |
Output is correct |
5 |
Correct |
2 ms |
560 KB |
Output is correct |
6 |
Correct |
10 ms |
876 KB |
Output is correct |
7 |
Correct |
17 ms |
1388 KB |
Output is correct |
8 |
Correct |
14 ms |
1388 KB |
Output is correct |
9 |
Correct |
5 ms |
1388 KB |
Output is correct |
10 |
Correct |
20 ms |
1388 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
1388 KB |
Output is correct |
2 |
Correct |
2 ms |
1388 KB |
Output is correct |
3 |
Correct |
3 ms |
1388 KB |
Output is correct |
4 |
Correct |
2 ms |
1388 KB |
Output is correct |
5 |
Correct |
2 ms |
1388 KB |
Output is correct |
6 |
Correct |
7 ms |
1388 KB |
Output is correct |
7 |
Correct |
15 ms |
1388 KB |
Output is correct |
8 |
Correct |
12 ms |
1388 KB |
Output is correct |
9 |
Correct |
6 ms |
1388 KB |
Output is correct |
10 |
Correct |
15 ms |
1388 KB |
Output is correct |
11 |
Correct |
3 ms |
1388 KB |
Output is correct |
12 |
Correct |
3 ms |
1388 KB |
Output is correct |
13 |
Correct |
31 ms |
2428 KB |
Output is correct |
14 |
Correct |
2 ms |
2428 KB |
Output is correct |
15 |
Correct |
27 ms |
2428 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2428 KB |
Output is correct |
2 |
Correct |
2 ms |
2428 KB |
Output is correct |
3 |
Correct |
3 ms |
2428 KB |
Output is correct |
4 |
Correct |
3 ms |
2428 KB |
Output is correct |
5 |
Correct |
2 ms |
2428 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
2428 KB |
Output is correct |
2 |
Correct |
3 ms |
2428 KB |
Output is correct |
3 |
Correct |
2 ms |
2428 KB |
Output is correct |
4 |
Correct |
2 ms |
2428 KB |
Output is correct |
5 |
Correct |
2 ms |
2428 KB |
Output is correct |
6 |
Correct |
2 ms |
2428 KB |
Output is correct |
7 |
Correct |
3 ms |
2428 KB |
Output is correct |
8 |
Correct |
3 ms |
2428 KB |
Output is correct |
9 |
Correct |
3 ms |
2428 KB |
Output is correct |
10 |
Correct |
3 ms |
2428 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2428 KB |
Output is correct |
2 |
Correct |
2 ms |
2428 KB |
Output is correct |
3 |
Correct |
2 ms |
2428 KB |
Output is correct |
4 |
Correct |
2 ms |
2428 KB |
Output is correct |
5 |
Correct |
2 ms |
2428 KB |
Output is correct |
6 |
Correct |
3 ms |
2428 KB |
Output is correct |
7 |
Correct |
3 ms |
2428 KB |
Output is correct |
8 |
Correct |
3 ms |
2428 KB |
Output is correct |
9 |
Correct |
3 ms |
2428 KB |
Output is correct |
10 |
Correct |
3 ms |
2428 KB |
Output is correct |
11 |
Correct |
17 ms |
2428 KB |
Output is correct |
12 |
Correct |
19 ms |
2468 KB |
Output is correct |
13 |
Correct |
20 ms |
2468 KB |
Output is correct |
14 |
Correct |
15 ms |
2468 KB |
Output is correct |
15 |
Correct |
31 ms |
2520 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2520 KB |
Output is correct |
2 |
Correct |
3 ms |
2520 KB |
Output is correct |
3 |
Correct |
3 ms |
2520 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2520 KB |
Output is correct |
2 |
Correct |
3 ms |
2520 KB |
Output is correct |
3 |
Correct |
3 ms |
2520 KB |
Output is correct |
4 |
Correct |
2 ms |
2520 KB |
Output is correct |
5 |
Correct |
2 ms |
2520 KB |
Output is correct |
6 |
Correct |
2 ms |
2520 KB |
Output is correct |
7 |
Correct |
3 ms |
2520 KB |
Output is correct |
8 |
Correct |
4 ms |
2520 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
2520 KB |
Output is correct |
2 |
Correct |
3 ms |
2520 KB |
Output is correct |
3 |
Correct |
3 ms |
2520 KB |
Output is correct |
4 |
Correct |
2 ms |
2520 KB |
Output is correct |
5 |
Correct |
2 ms |
2520 KB |
Output is correct |
6 |
Correct |
3 ms |
2520 KB |
Output is correct |
7 |
Correct |
2 ms |
2520 KB |
Output is correct |
8 |
Correct |
2 ms |
2520 KB |
Output is correct |
9 |
Correct |
70 ms |
4456 KB |
Output is correct |
10 |
Correct |
46 ms |
4456 KB |
Output is correct |
11 |
Correct |
24 ms |
4456 KB |
Output is correct |
12 |
Correct |
24 ms |
4456 KB |
Output is correct |
13 |
Correct |
6 ms |
4456 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
4456 KB |
Output is correct |
2 |
Correct |
2 ms |
4456 KB |
Output is correct |
3 |
Correct |
2 ms |
4456 KB |
Output is correct |
4 |
Correct |
2 ms |
4456 KB |
Output is correct |
5 |
Correct |
2 ms |
4456 KB |
Output is correct |
6 |
Correct |
2 ms |
4456 KB |
Output is correct |
7 |
Correct |
3 ms |
4456 KB |
Output is correct |
8 |
Correct |
3 ms |
4456 KB |
Output is correct |
9 |
Correct |
65 ms |
5712 KB |
Output is correct |
10 |
Correct |
47 ms |
5712 KB |
Output is correct |
11 |
Correct |
21 ms |
5712 KB |
Output is correct |
12 |
Correct |
24 ms |
5712 KB |
Output is correct |
13 |
Correct |
8 ms |
5712 KB |
Output is correct |
14 |
Correct |
94 ms |
8384 KB |
Output is correct |
15 |
Correct |
121 ms |
9724 KB |
Output is correct |
16 |
Correct |
19 ms |
9724 KB |
Output is correct |
17 |
Correct |
69 ms |
9724 KB |
Output is correct |
18 |
Correct |
38 ms |
9724 KB |
Output is correct |