#include<bits/stdc++.h>
#define endl '\n'
#include "gondola.h"
using namespace std;
const long long int maxn=1000000009;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
struct cell
{
int v,st;
};
bool cmp(cell a1,cell a2)
{
return a1.st<a2.st;
}
int n,a[200005],ind[200005],se[200005];
cell c[200005];
vector<bool>used(1000000009);
int valid(int n,int seq[])
{
int br=0;
for(int i=1; i<=n; i++)
{
a[i]=seq[i-1];
}
for(int i=1; i<=n; i++)
{
if(a[i]<=n)
{
if(!br)br=a[i];
else
{
if(a[i]!=br)
{
return 0;
}
}
}
if(used[a[i]])
{
return 0;
}
used[a[i]]=1;
if(br)br++;
if(br>n)br=1;
}
for(int i=n+2; i<=250000; i++)
{
if(used[i]&&!used[i-1])
{
return 0;
}
}
return 1;
}
int replacement(int n, int seq[], int rseq[])
{
int st=1,val=1,next=n+1;
for(int i=1; i<=n; i++)
{
a[i]=seq[i-1];
}
for(int i=1; i<=n; i++)
{
if(a[i]<=n)
{
st=i;
val=a[i];
break;
}
}
for(int i=st; i<=n; i++)
{
ind[i]=val;
val++;
if(val>n)val=1;
}
for(int i=1; i<st; i++)
{
ind[i]=val;
val++;
}
for(int i=1; i<=n; i++)
{
c[i].v=ind[i];
c[i].st=a[i];
}
sort(c+1,c+n+1,cmp);
int br=0;
for(int i=1; i<=n; i++)
{
if(c[i].st>n)
{
while(c[i].v!=c[i].st)
{
rseq[br]=c[i].v;
br++;
c[i].v=next;
next++;
}
}
}
return br;
}
long long int fup(long long int base,long long int pow)
{
long long int otg=1;
for(int i=0; i<=30; i++)
{
if(pow&(1<<i))
{
otg*=base;
otg=otg%maxn;
}
base*=base;
base=base%maxn;
}
return otg;
}
bool check()
{
int br=0;
for(int i=1; i<=n; i++)
{
if(a[i]<=n)
{
if(!br)br=a[i];
else
{
if(a[i]!=br)
{
return 0;
}
}
}
if(used[a[i]])
{
return 0;
}
used[a[i]]=1;
if(br)br++;
if(br>n)br=1;
}
return 1;
}
int countReplacement(int n, int seq[])
{
long long int otg=1,now=n,f=0;
for(int i=1; i<=n; i++)
{
a[i]=seq[i-1];
if(a[i]<=n)f=1;
}
if(!check())return 0;
sort(a+1,a+n+1);
for(int i=1; i<=n; i++)
{
if(a[i]>now)
{
otg=otg*fup(n-i+1,a[i]-now-1);
otg=otg%maxn;
now=a[i];
}
}
if(f)return otg;
else return (otg*n)%maxn;
}
void test()
{
cin>>n;
long long int otg=1,now=n;
for(int i=1; i<=n; i++)
{
cin>>a[i];
se[i-1]=a[i];
}
if(!check())
{
cout<<0<<endl;
return;
}
sort(a+1,a+n+1);
for(int i=1; i<=n; i++)
{
if(a[i]>n)
{
otg=otg*fup(n-i+1,a[i]-now-1);
otg=otg%maxn;
now=a[i];
}
}
cout<<otg<<endl;
}
/*int main()
{
speed();
test();
return 0;
}
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
122716 KB |
Output is correct |
2 |
Correct |
29 ms |
122716 KB |
Output is correct |
3 |
Correct |
29 ms |
122532 KB |
Output is correct |
4 |
Correct |
28 ms |
122704 KB |
Output is correct |
5 |
Correct |
33 ms |
122796 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
30 ms |
122708 KB |
Output is correct |
2 |
Correct |
28 ms |
122716 KB |
Output is correct |
3 |
Correct |
27 ms |
122588 KB |
Output is correct |
4 |
Correct |
27 ms |
122708 KB |
Output is correct |
5 |
Correct |
34 ms |
122708 KB |
Output is correct |
6 |
Correct |
32 ms |
122940 KB |
Output is correct |
7 |
Correct |
32 ms |
123224 KB |
Output is correct |
8 |
Correct |
34 ms |
123228 KB |
Output is correct |
9 |
Correct |
29 ms |
122716 KB |
Output is correct |
10 |
Correct |
35 ms |
123160 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
122708 KB |
Output is correct |
2 |
Correct |
28 ms |
122704 KB |
Output is correct |
3 |
Correct |
34 ms |
122708 KB |
Output is correct |
4 |
Correct |
30 ms |
122712 KB |
Output is correct |
5 |
Correct |
30 ms |
122708 KB |
Output is correct |
6 |
Correct |
35 ms |
122976 KB |
Output is correct |
7 |
Correct |
36 ms |
123400 KB |
Output is correct |
8 |
Correct |
34 ms |
123296 KB |
Output is correct |
9 |
Correct |
31 ms |
122708 KB |
Output is correct |
10 |
Correct |
34 ms |
123216 KB |
Output is correct |
11 |
Correct |
34 ms |
122712 KB |
Output is correct |
12 |
Correct |
29 ms |
122708 KB |
Output is correct |
13 |
Correct |
33 ms |
122968 KB |
Output is correct |
14 |
Correct |
30 ms |
122716 KB |
Output is correct |
15 |
Correct |
36 ms |
123416 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
122716 KB |
Output is correct |
2 |
Correct |
29 ms |
122704 KB |
Output is correct |
3 |
Correct |
29 ms |
122708 KB |
Output is correct |
4 |
Correct |
29 ms |
122708 KB |
Output is correct |
5 |
Correct |
34 ms |
122704 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
122716 KB |
Output is correct |
2 |
Correct |
33 ms |
122640 KB |
Output is correct |
3 |
Correct |
30 ms |
122708 KB |
Output is correct |
4 |
Correct |
31 ms |
122712 KB |
Output is correct |
5 |
Correct |
29 ms |
122712 KB |
Output is correct |
6 |
Correct |
35 ms |
122704 KB |
Output is correct |
7 |
Correct |
30 ms |
122716 KB |
Output is correct |
8 |
Correct |
29 ms |
122752 KB |
Output is correct |
9 |
Correct |
31 ms |
122716 KB |
Output is correct |
10 |
Correct |
29 ms |
122712 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
122656 KB |
Output is correct |
2 |
Correct |
30 ms |
122716 KB |
Output is correct |
3 |
Correct |
29 ms |
122740 KB |
Output is correct |
4 |
Correct |
29 ms |
122688 KB |
Output is correct |
5 |
Correct |
30 ms |
122716 KB |
Output is correct |
6 |
Correct |
35 ms |
122700 KB |
Output is correct |
7 |
Correct |
31 ms |
122712 KB |
Output is correct |
8 |
Correct |
30 ms |
122708 KB |
Output is correct |
9 |
Correct |
29 ms |
122708 KB |
Output is correct |
10 |
Correct |
29 ms |
122704 KB |
Output is correct |
11 |
Correct |
40 ms |
124240 KB |
Output is correct |
12 |
Correct |
40 ms |
124500 KB |
Output is correct |
13 |
Correct |
37 ms |
123988 KB |
Output is correct |
14 |
Correct |
37 ms |
124276 KB |
Output is correct |
15 |
Correct |
41 ms |
124776 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
122708 KB |
Output is correct |
2 |
Correct |
29 ms |
122732 KB |
Output is correct |
3 |
Correct |
28 ms |
122716 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
122604 KB |
Output is correct |
2 |
Correct |
34 ms |
122600 KB |
Output is correct |
3 |
Correct |
27 ms |
122716 KB |
Output is correct |
4 |
Correct |
28 ms |
122724 KB |
Output is correct |
5 |
Correct |
28 ms |
122616 KB |
Output is correct |
6 |
Correct |
28 ms |
122708 KB |
Output is correct |
7 |
Correct |
26 ms |
122704 KB |
Output is correct |
8 |
Correct |
27 ms |
122716 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
122708 KB |
Output is correct |
2 |
Correct |
33 ms |
122708 KB |
Output is correct |
3 |
Correct |
28 ms |
122708 KB |
Output is correct |
4 |
Correct |
29 ms |
122704 KB |
Output is correct |
5 |
Correct |
32 ms |
122516 KB |
Output is correct |
6 |
Correct |
28 ms |
122716 KB |
Output is correct |
7 |
Correct |
28 ms |
122564 KB |
Output is correct |
8 |
Correct |
28 ms |
122704 KB |
Output is correct |
9 |
Correct |
42 ms |
123204 KB |
Output is correct |
10 |
Correct |
40 ms |
123220 KB |
Output is correct |
11 |
Correct |
34 ms |
122844 KB |
Output is correct |
12 |
Correct |
34 ms |
122960 KB |
Output is correct |
13 |
Correct |
29 ms |
122744 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
122716 KB |
Output is correct |
2 |
Correct |
29 ms |
122708 KB |
Output is correct |
3 |
Correct |
34 ms |
122712 KB |
Output is correct |
4 |
Correct |
33 ms |
122752 KB |
Output is correct |
5 |
Correct |
31 ms |
122704 KB |
Output is correct |
6 |
Correct |
28 ms |
122712 KB |
Output is correct |
7 |
Correct |
27 ms |
122716 KB |
Output is correct |
8 |
Correct |
33 ms |
122660 KB |
Output is correct |
9 |
Correct |
44 ms |
123316 KB |
Output is correct |
10 |
Correct |
41 ms |
123224 KB |
Output is correct |
11 |
Correct |
35 ms |
122716 KB |
Output is correct |
12 |
Correct |
36 ms |
122964 KB |
Output is correct |
13 |
Correct |
32 ms |
122712 KB |
Output is correct |
14 |
Correct |
54 ms |
123988 KB |
Output is correct |
15 |
Correct |
52 ms |
124244 KB |
Output is correct |
16 |
Correct |
32 ms |
122964 KB |
Output is correct |
17 |
Correct |
43 ms |
123680 KB |
Output is correct |
18 |
Correct |
39 ms |
123184 KB |
Output is correct |