이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#include "gondola.h"
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define N 100005
int valid(int n, int a[]){
int i,mod=1e9;
bitset<250005> vis;
for(i=0;i<n;i++){
if(vis[a[i]])return 0;
vis[a[i]]=true;
if(a[i]>n)continue;
if(mod==1e9)mod=(i-a[i]+n)%n;
else if(mod!=(i-a[i]+n)%n)return 0;
}
return 1;
}
int replacement(int n, int a[], int b[]){
int i,j,now,last,cnt;
vector<pair<int,int>> v;
for(i=0;i<n;i++)if(a[i]>n)v.push_back({a[i],i});
for(i=0;i<n;i++){
if(a[i]<=n){
now=a[i];
for(j=i+1;j<n;j++){
now++;
if(now==n+1)now=1;
a[j]=now;
}
for(j=0;j<i;j++){
now++;
if(now==n+1)now=1;
a[j]=now;
}
break;
}
}
if(i==n)for(i=0;i<n;i++)a[i]=i+1;
sort(v.begin(),v.end());
i=0;
last=n;
for(auto [now,x]:v){
cnt=now-last;
while(cnt--)b[i++]=a[x],a[x]=i+n;
last=now;
}
return i;
}
long long mod=1e9+9;
long long bp(long long a,long long b){
if(b==0)return 1;
long long temp=bp(a,b/2);
if(b%2)return temp*temp%mod*a%mod;
return temp*temp%mod;
}
int countReplacement(int n, int a[]){
int i,len,last;
long long ans=1;
vector<int> v;
if(!valid(n,a))return 0;
for(i=0;i<n;i++)if(a[i]>n)v.push_back(a[i]);
sort(v.begin(),v.end());
len=v.size();
last=n;
for(i=0;i<len;i++){
ans=ans*bp(len-i,v[i]-last-1)%mod;
last=v[i];
}
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |