| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 152492 | Nightlight | 곤돌라 (IOI14_gondola) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "gondola.h"
#include <bits/stdc++.h>
#define MOD 1000000009;
using namespace std;
int exist[250001];
int valid(int n, int inputSeq[])
{
int idx = 0;
for(int i = 0; i < n; i++){
if(!idx && inputSeq[i] <= n)
idx = inputSeq[i];
else{
if(idx > n)idx = 1;
if(inputSeq[i] <= n && inputSeq[i] != idx)
return 0;
idx++;
}
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int len = 0, idx = 0, av = 0, MAX = 0, MAXid;
for(int i = 0; i < n; i++){
if(gondolaSeq[i] <= n){
idx = gondolaSeq[i] - i;
if(idx < 1) idx += n;
break;
}
}
if(!idx)idx = 1;
for(int i = 0; i < n; i++){
if(idx > n)idx = 1;
if(gondolaSeq[i] > MAX){
MAX = gondolaSeq[i];
MAXid = idx;
}
if(gondolaSeq[i] > n){
exist[gondolaSeq[i]] = idx;
// cout << gondolaSeq[i] << " " << exist[gondolaSeq[i]] << "\n";
}
idx++;
}
if(MAX == n)return 0;
else{
int j = 0, MAXin = 0, last = 0;
exist[MAX] = 0;
for(int i = n+1; i <= MAX; i++){
// cout << i << " " << exist[i] << "\n";
if(exist[i]){
replacementSeq[i-n-1] = exist[i];
}else{
if(!MAXin){
replacementSeq[i-n-1] = MAXid;
MAXin = 1;
}else{
replacementSeq[i-n-1] = last;
}
last = i;
}
}
}
return MAX - n;
}
//----------------------
vector<int> replaced;
long long int pow( long long int a, long long int x ){
if( x == 0 || a == 1 )
return 1;
if( x % 2 )
return ( pow( a, x - 1 ) * a ) % mod;
long long int h = pow( a, x/2 );
return ( h * h ) % mod;
}
int countReplacement(int n, int inputSeq[])
{
int idx = 0;
replaced.push_back(n);
for(int i = 0; i < n; i++){
if(!idx && inputSeq[i] <= n)
idx = inputSeq[i];
else{
if(idx > n)idx = 1;
if(inputSeq[i] > n)replaced.push_back[inputSeq[i]];
else if(inputSeq[i] <= n && inputSeq[i] != idx)
return 0;
idx++;
}
}
sort(replaced.begin(), replaced.end());
long long ans = idx ? n : 1;
if(!idx){
ans *= n;
}
for(int i = 1; i < replaced.size(); i++){
ans *= pow(replaced.size() - i + 1,replaced[i] - replaced[i-1]);
ans %= MOD;
}
return ans;
}