| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 582261 | kamelfanger83 | 곤돌라 (IOI14_gondola) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
#include "gondola.h"
#include <limits>
#include <numeric>
#include <algorithm>
using namespace std;
int mode = 1e9+9;
int valid(int n, int inputSeq[]){
int one = numeric_limits<int>::min();
vector<bool> used (250001, false);
for(int c = 0; c < n; c++){
if(inputSeq[c] <= n){
if(one == numeric_limits<int>::min()) one = c - inputSeq[c] + 1;
if((c - one + 1) % n != inputSeq[c] % n) return 0;
}
else{
if(used[inputSeq[c]]) return 0;
used[inputSeq[c]] = true;
}
}
return 1;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[]){
int one = 0;
for(int c = 0; c < n; c++){
if(gondolaSeq[c] <= n) one = c - gondolaSeq[c] + 1;
}
vector<int> ind (n); iota(ind.begin(), ind.end(), 0);
auto gcomp = [&](int u, int v){return gondolaSeq[u] < gondolaSeq[v];};
sort(ind.begin(), ind.end(), gcomp);
int repg = n;
int l = 0;
vector<int> ac (n);
for(int acer = 0; acer < n; acer++){
int num = (acer - one + 1 + n) % n;
if(num == 0) num = n;
ac[acer] = num;
}
for(int rep : ind){
while(repg < gondolaSeq[rep]){
replacementSeq[l++] = ac[rep];
repg++;
ac[rep] = repg;
}
}
return l;
}
int fastpow(long long b, long long e){
long long res = 1;
for(;e != 0;e>>=1){
if(e&1) res *= b;
res %= mode;
b *= b;
b %= mode;
}
return res;
}
int countReplacement(int n, int inputSeq[]){
if(!valid(n, inputSeq)) return 0;
vector<int> ind (n); iota(ind.begin(), ind.end(), 0);
auto gcomp = [&](int u, int v){return inputSeq[u] < inputSeq[v];};
sort(ind.begin(), ind.end(), gcomp);
int repg = n + 1;
int p = 1;
for(int ig = 0; ig < n; ig++){
if(repg < inputSeq[ind[ig]] - 1){
p *= fastpow(n-ig,inputSeq[ind[ig]] - repg);
p %= mode;
}
if(inputSeq[ind[ig]] > n) repg = inputSeq[ind[ig]];
}
return p;
}
int main(){
int seq [14] = {6, 94, 8, 9, 10, 93, 12, 13, 95, 1, 2, 3, 4, 5};
cout << countReplacement(14, seq);
}