| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 169195 | DavidDamian | 곤돌라 (IOI14_gondola) | C++11 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "gondola.h"
#include<vector>
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
///Permutations
///Binary Exponentiation
///Determine whether a sequence is a gondola sequence, a possible replacement sequence and the number of replacement sequences
map<int,int> used;
int valid(int n, int inputSeq[])
{
int corresponding=1;
int id_less_n=0;
for(int i=0;i<n;i++){
if(inputSeq[i]<=n){
id_less_n=i;
corresponding=inputSeq[i];
break;
}
}
for(int i=id_less_n;i<n+id_less_n;i++){
if(used[ inputSeq[i%n] ]) return 0;
used[ inputSeq[i%n] ]=1;
if(inputSeq[i%n]>n){
corresponding=(corresponding%n)+1;
continue;
}
if(inputSeq[i%n]!=corresponding){
return 0;
}
corresponding=(corresponding%n)+1;
}
return 1;
}
typedef pair<int,int> pii;
//First is equal to the actual gondola
//Second is equal to the original gondola
bool byActual(pii a,pii b)
{
return a.first<b.first;
}
vector<pii> broken;
void getBrokenGondolas(int n,int gondolaSeq[]) ///Return a vector with broken gondolas in in increasing order
{
int corresponding=1;
int id_less_n=0;
for(int i=0;i<n;i++){
if(gondolaSeq[i]<=n){
id_less_n=i;
corresponding=gondolaSeq[i];
break;
}
}
for(int i=id_less_n;i<n+id_less_n;i++){
if(gondolaSeq[i%n]>n) broken.push_back(pii(gondolaSeq[i%n],corresponding));
corresponding=(corresponding%n)+1;
}
sort(broken.begin(),broken.end(),byActual);
}
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
getBrokenGondolas(n,gondolaSeq);
int L=0;
int act=n+1;
for(pii x: broken){
replacementSeq[L++]=x.second; //We add the original
while(act<x.first){
replacementSeq[L++]=act++; //Adds the intermediate gondolas
}
act++; //We update act since it is equal to the number of replaced gondola
}
return L;
}
typedef long long int ll;
ll mod=1000000009;
long long binpow(long long a, long long b) {
a %= m;
long long res = 1;
while (b > 0) {
if (b & 1)
res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
int countReplacement(int n, int inputSeq[])
{
if(!valid(n,inputSeq)) return 0;
ll total=1;
getBrokenGondolas(n,inputSeq);
ll act=n+1;
ll N=broken.size();
for(ll i=0;i<N;i++){
ll x=broken[i].first;
ll k=x-act; //This is the number of numbers that have N-i choices
total=(total*binpow((ll)(N-i),k))%mod; //So we compute permutation with repetitions, of choices ((N-i)^k)
act=x+1;
}
return total;
}