| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 835814 | 2023-08-23T20:52:20 Z | 7mody | 곤돌라 (IOI14_gondola) | C++17 | 0 ms | 0 KB |
#include "gondola.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 250005;
const int mod=1e9+9;
map<int,int> mp;
ll power(ll a,ll n){
ll res=1;
while(n){
if(n&1) res=(res*n)%mod;
a=(a*a) % mod;
n>>=1;
}
return res;
}
int valid(int n, int arr[]){
int start=-1;
for(int i=0; i < n;i++){
if(mp[arr[i]]) return 0;
mp[arr[i]]=true;
if(arr[i]<=n){
int curr=(i-arr[i]+1+n)%n;
if(start==-1) start=curr;
else if(start!=curr) return 0;
}
}
return 1;
}
int replacement(int n, int arr[], int res[]){
int start=-1;
deque<int> dq(n);
for(int i=0; i < n;i++){
if(arr[i]<=n) start=(i-arr[i]+1+n)%n;
dq[i]=arr[i];
}
while(start){
dq.push_back(dq.front());
dq.pop_front();
start--;
}
vector<pair<int,int>> ans(n);
for(int i=0; i < n;i++){
ans.push_back({dq[i],i});
}
int size=0;
int curr=n+1;
for(int i=0; i < n;i++){
if(dq[i]<=n) continue;
res[size++]=ans[i].second+1;
while(curr < ans[i].first) res[size++]=curr++;
curr++;
}
return size;
}
ll countReplacement(int n, int arr[]){
if(!valid(n,arr)) return 0;
vector<ll> vec;
ll curr=n;
ll res=1;
ll last=n;
for(int i=0; i < n;i++){
if(arr[i]<=n) curr--;
else vec.push_back(arr[i]);
}
if(curr==n) res=n;
for(ll x : vec){
res=(res*power(curr,x-last-1))%mod;
last=x;
}
return res;
}