#include<bits/stdc++.h>
#include "gondola.h"
using namespace std;
const int MAXN = 1E5+5 , mod = 1E9 + 9;
int n,a[MAXN];
int valid(int n1, int inputSeq[]) {
n = n1;
int pos = -1;
for (int i = 0; i < n; i++) {
a[i] = inputSeq[i];
if (a[i] <= n)
pos = i;
}
if (pos != -1) {
int x = (a[pos] - pos - 1)%n;
if (x <0) x+= n;
int b[MAXN];
for (int i = 0; i < n; i++) {
b[(x + i)%n] = a[i];
}
for (int i = 0;i < n; i++)
a[i] = b[i];
}
set<int> s;
for (int i = 0; i < n; i++) {
if (a[i] < n) {
if (a[i] != i + 1) return 0;
}
s.insert(a[i]);
}
if (s.size() != n) return 0;
return 1;
}
bool cmp(int x,int y) {
return a[x-1] < a[y-1];
}
int replacement(int n1, int gondolaSeq[], int replacementSeq[]){
bool c = valid(n1,gondolaSeq);
vector<int> v;
for (int i = 0; i < n ;i++) {
if (a[i] > n) {
v.push_back(a[i]);
}
}
sort (v.begin(),v.end());
vector<int> b(n+1);
vector<int> g;
for (int i = 0; i < n; i++)
if (a[i] <= n) b[a[i]] = 1;
for (int i = 1; i <= n; i++)
if (!b[i]) {
g.push_back(i);
}
int cnt = 0;
int val = n+1;
vector<bool> good(100000000);
for (int i = 0; i < v.size(); i++)
good [v[i]] = 1;
sort(g.begin(),g.end(),cmp);
if (v.size() == 0) return 0;
int mx = v.back() + 1;
for (int i = 0;i < g.size(); i++) {
while (!good[ g[i] ]) {
replacementSeq[cnt] = g[i];
g[i] = val;
val++;
cnt++;
}
}
return cnt;
}
int pw(int a,int n) {
int y = 1;
for (; n; n/=2) {
if (n & 1) y= 1ll*y*a%mod;
a = 1ll*a*a%mod;
}
return y;
}
int countReplacement(int n1, int inputSeq[]) {
if (valid(n1,inputSeq) == 0) return 0;
int ans = 1;
vector<int> v;
for (int i = 0; i < n; i++) {
if (a[i] > n) v.push_back(a[i]);
}
sort(v.begin(),v.end());
int last = n;
for (int i = 0; i < n; i++) {
ans= 1ll*ans*pw(n - i,v[i] - last - 1)%mod;
last = v[i];
}
return ans;
}
/*
main() {
int n;
cin >> n;
int inputseq[n];
int s[100000];
for (int i = 0;i < n; i++)
cin >> inputseq[i];
cout << replacement(n,inputseq,s);
} */
Compilation message
gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:31:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (s.size() != n) return 0;
~~~~~~~~~^~~~
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:59:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < v.size(); i++)
~~^~~~~~~~~~
gondola.cpp:64:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0;i < g.size(); i++) {
~~^~~~~~~~~~
gondola.cpp:39:7: warning: unused variable 'c' [-Wunused-variable]
bool c = valid(n1,gondolaSeq);
^
gondola.cpp:63:6: warning: unused variable 'mx' [-Wunused-variable]
int mx = v.back() + 1;
^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
19 ms |
2688 KB |
Output is correct |
7 |
Correct |
19 ms |
1408 KB |
Output is correct |
8 |
Correct |
29 ms |
4608 KB |
Output is correct |
9 |
Correct |
13 ms |
1792 KB |
Output is correct |
10 |
Correct |
34 ms |
5368 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
18 ms |
2688 KB |
Output is correct |
7 |
Correct |
19 ms |
1408 KB |
Output is correct |
8 |
Correct |
31 ms |
4608 KB |
Output is correct |
9 |
Correct |
12 ms |
1792 KB |
Output is correct |
10 |
Correct |
33 ms |
5248 KB |
Output is correct |
11 |
Correct |
5 ms |
384 KB |
Output is correct |
12 |
Correct |
5 ms |
384 KB |
Output is correct |
13 |
Correct |
12 ms |
896 KB |
Output is correct |
14 |
Correct |
4 ms |
384 KB |
Output is correct |
15 |
Correct |
19 ms |
1408 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
12544 KB |
Output is correct |
2 |
Correct |
12 ms |
12544 KB |
Output is correct |
3 |
Correct |
11 ms |
12544 KB |
Output is correct |
4 |
Correct |
11 ms |
12544 KB |
Output is correct |
5 |
Correct |
11 ms |
12544 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
12544 KB |
Output is correct |
2 |
Correct |
11 ms |
12544 KB |
Output is correct |
3 |
Correct |
11 ms |
12544 KB |
Output is correct |
4 |
Correct |
11 ms |
12672 KB |
Output is correct |
5 |
Correct |
11 ms |
12544 KB |
Output is correct |
6 |
Correct |
11 ms |
12544 KB |
Output is correct |
7 |
Correct |
11 ms |
12672 KB |
Output is correct |
8 |
Correct |
11 ms |
12672 KB |
Output is correct |
9 |
Correct |
11 ms |
12672 KB |
Output is correct |
10 |
Correct |
12 ms |
12544 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
12544 KB |
Output is correct |
2 |
Correct |
11 ms |
12544 KB |
Output is correct |
3 |
Correct |
11 ms |
12544 KB |
Output is correct |
4 |
Correct |
11 ms |
12544 KB |
Output is correct |
5 |
Correct |
12 ms |
12544 KB |
Output is correct |
6 |
Correct |
10 ms |
12544 KB |
Output is correct |
7 |
Correct |
12 ms |
12672 KB |
Output is correct |
8 |
Correct |
11 ms |
12544 KB |
Output is correct |
9 |
Correct |
11 ms |
12672 KB |
Output is correct |
10 |
Correct |
11 ms |
12544 KB |
Output is correct |
11 |
Correct |
37 ms |
17272 KB |
Output is correct |
12 |
Correct |
43 ms |
18040 KB |
Output is correct |
13 |
Correct |
39 ms |
13856 KB |
Output is correct |
14 |
Correct |
40 ms |
17272 KB |
Output is correct |
15 |
Correct |
39 ms |
13924 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |