#include "gondola.h"
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(ll i=a,ioi=b;i<ioi;i++)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define imp(v) {for(auto fdgkj:v)cout<<fdgkj<<" ";cout<<"\n";}
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
void rotate(vector<ll>&a, ll x){
rotate(a.begin(),a.begin()+x,a.end());
}
int valid(int n, int A[]){
vector<ll>a(n);
fore(i,0,n)a[i]=A[i]-1;
set<ll>st;
fore(i,0,n)st.insert(a[i]);
if(SZ(st)<n)return 0;
ll done=0;
fore(i,0,n)if(!done&&a[i]<n){
ll v=a[i];
rotate(a,i);
rotate(a,(n-v)%n),done=1;
}
if(!done)return 1;
ll flag=1;
fore(i,0,n){
ll fi=a[i]>=n||a[i]==i;
flag&=fi;
}
return flag;
}
int replacement(int n, int A[], int ret[]){
vector<ll>a(n);
fore(i,0,n)a[i]=A[i]-1;
set<ll>st;
fore(i,0,n)st.insert(a[i]);
assert(SZ(st)==n);
ll done=0;
// imp(a);
fore(i,0,n)if(!done&&a[i]<n){
ll v=a[i];
rotate(a,i);
rotate(a,(n-v)%n),done=1;
}
// imp(a);
vector<ii>b;
fore(i,0,n)if(a[i]>=n)b.pb({a[i],i});
fore(i,0,n)a[i]=i;
sort(ALL(b));
ll p=-1;
vector<ll>res;
if(!SZ(b))return 0;
// for(auto [c,v]:b)cout<<c<<","<<v<<" ";;cout<<"\n";
fore(k,n,b.back().fst+1){
// cout<<k<<": "<<p<<endl;
ll i=b[p+1].snd;
res.pb(a[i]);
a[i]=k;
if(b[p+1].fst==k)p++;
}
fore(i,0,SZ(res))ret[i]=res[i]+1;
return SZ(res);
}
const ll MOD=1e9+9;
// ll add(ll a, ll b){a+=b;if(a>=MOD)a-=MOD;return a;}
// ll sub(ll a, ll b){a-=b;if(a<0)a+=MOD;return a;}
ll mul(ll a, ll b){return a*b%MOD;}
ll fpow(ll b, ll e){
ll res=1;
while(e){
if(e&1)res=mul(res,b);
b=mul(b,b),e>>=1;
}
return res;
}
int countReplacement(int n, int A[]){
vector<ll>a(n);
fore(i,0,n)a[i]=A[i]-1;
if(!valid(n,A))return 0;
ll done=0;
// imp(a);
fore(i,0,n)if(!done&&a[i]<n){
ll v=a[i];
rotate(a,i);
rotate(a,(n-v)%n),done=1;
}
// imp(a);
vector<ll>b;
fore(i,0,n)if(a[i]>=n)b.pb(a[i]);
sort(ALL(b));
// if(!SZ(b))return 1;
ll res=1;
fore(i,0,SZ(b)){
ll dif=b[i]-(i?b[i-1]:n-1)-1;
res=mul(res,fpow(SZ(b)-i,dif));
}
if(!done)res=mul(res,n);
return res;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
360 KB |
Output is correct |
4 |
Correct |
0 ms |
360 KB |
Output is correct |
5 |
Correct |
0 ms |
360 KB |
Output is correct |
6 |
Correct |
8 ms |
2876 KB |
Output is correct |
7 |
Correct |
22 ms |
4944 KB |
Output is correct |
8 |
Correct |
15 ms |
4956 KB |
Output is correct |
9 |
Correct |
5 ms |
1896 KB |
Output is correct |
10 |
Correct |
21 ms |
5720 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
600 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
440 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
8 ms |
2832 KB |
Output is correct |
7 |
Correct |
20 ms |
4836 KB |
Output is correct |
8 |
Correct |
14 ms |
4956 KB |
Output is correct |
9 |
Correct |
5 ms |
1864 KB |
Output is correct |
10 |
Correct |
19 ms |
5780 KB |
Output is correct |
11 |
Correct |
0 ms |
344 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
11 ms |
2552 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
25 ms |
5968 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
360 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
360 KB |
Output is correct |
2 |
Correct |
0 ms |
360 KB |
Output is correct |
3 |
Correct |
0 ms |
360 KB |
Output is correct |
4 |
Correct |
1 ms |
360 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
604 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
600 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
440 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
612 KB |
Output is correct |
11 |
Correct |
15 ms |
5480 KB |
Output is correct |
12 |
Correct |
18 ms |
6248 KB |
Output is correct |
13 |
Correct |
17 ms |
4196 KB |
Output is correct |
14 |
Correct |
17 ms |
5432 KB |
Output is correct |
15 |
Correct |
18 ms |
3936 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
360 KB |
Output is correct |
2 |
Correct |
0 ms |
360 KB |
Output is correct |
3 |
Correct |
0 ms |
612 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
360 KB |
Output is correct |
2 |
Correct |
0 ms |
360 KB |
Output is correct |
3 |
Correct |
1 ms |
360 KB |
Output is correct |
4 |
Correct |
0 ms |
360 KB |
Output is correct |
5 |
Correct |
0 ms |
360 KB |
Output is correct |
6 |
Correct |
0 ms |
360 KB |
Output is correct |
7 |
Correct |
0 ms |
360 KB |
Output is correct |
8 |
Correct |
0 ms |
360 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
27 ms |
5724 KB |
Output is correct |
10 |
Correct |
21 ms |
4696 KB |
Output is correct |
11 |
Correct |
8 ms |
1992 KB |
Output is correct |
12 |
Correct |
10 ms |
2240 KB |
Output is correct |
13 |
Correct |
2 ms |
860 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
600 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
604 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
26 ms |
5724 KB |
Output is correct |
10 |
Correct |
21 ms |
4700 KB |
Output is correct |
11 |
Correct |
11 ms |
1996 KB |
Output is correct |
12 |
Correct |
10 ms |
2392 KB |
Output is correct |
13 |
Correct |
2 ms |
860 KB |
Output is correct |
14 |
Correct |
33 ms |
6648 KB |
Output is correct |
15 |
Correct |
37 ms |
7504 KB |
Output is correct |
16 |
Correct |
6 ms |
1628 KB |
Output is correct |
17 |
Correct |
25 ms |
5200 KB |
Output is correct |
18 |
Correct |
13 ms |
3164 KB |
Output is correct |