답안 #16453 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
16453	2015-08-25T07:42:34 Z	atomzeno	곤돌라 (IOI14_gondola)	C++	100 / 100	50 ms	6360 KB

gondola

#include "gondola.h"
#define MOD 1000000009
#include<algorithm>
using namespace std;
#define MX 200001
int d[MX],check[MX],D[MX];
int l,ind;
int valid(int n, int inputSeq[]){
    int i,cnt=0,ind;
    for(i=0;i<n;i++){check[i]=inputSeq[i];}
    for(i=0;i<n;i++){
        if(inputSeq[i]<=n){
            cnt=1;
            ind=(inputSeq[i]-1-i)+n;
            ind%=n;
            break;
        }
    }
    sort(check,check+n);
    for(i=1;i<n;i++){
        if(check[i]==check[i-1]){return 0;}
    }
    if(cnt==0){return 1;}
    for(i=0;i<n;i++){
        d[(ind+i)%n]=inputSeq[i];
    }
    for(i=0;i<n;i++){
        if(d[i]<=n&&d[i]!=(i+1)){
            return 0;
        }
    }
    return 1;
}
struct DT{
    int x,y;
    bool operator<(const DT&r)const{
        return r.x>x;
    }
}make[MX];
int replacement(int n, int gondolaSeq[], int replacementSeq[]){
    int ll=0,o=n,flag=0,indin,i,j;
    for(i=0;i<n;i++){
        if(gondolaSeq[i]<=n){
            flag=1;
            indin=gondolaSeq[i];
            break;
        }
    }
    if(flag==0){indin=1;}
    for(j=i;j<i+n;j++){
        make[j%n].x=gondolaSeq[j%n];
        if(indin>n){indin-=n;}
        make[j%n].y=indin++;
    }
    sort(make,make+n);
    for(i=0;i<n;){
        if(make[i].y>=make[i].x){
            i++;
            continue;
        }
        replacementSeq[ll++]=make[i].y;
        make[i].y=++o;
    }
    return ll;
}
long long int p,pp;
long long int a[33];
//----------------------
long long int calc(int x,int y){//x의 y승
    int i;
    a[0]=x%MOD;
    if(y==0){
        return 1;
    }
    for(i=1;i<=31;i++){
        p=(a[i-1]*a[i-1]);
        a[i]=p%MOD;
    }
    p=1;
    for(i=0;i<=31;i++){
        if((y&((long long int)1<<i))!=0){
            p=p*a[i];
            p=p%MOD;
        }
    }
    return p%MOD;
}
int countReplacement(int n, int inputSeq[]){
    int o=n,i,flag;
    long long int lll=0;
    pp=1;
    flag=0;
    lll=0;
    if(valid(n,inputSeq)==0){return 0;}
    for(i=0;i<n;i++){
        if(inputSeq[i]>n){
            D[lll++]=inputSeq[i];
        }
        else{flag=1;}
    }
    sort(D,D+lll);
    pp=1;
    for(i=0;i<lll;i++){
        pp=(pp*calc(lll-i,D[i]-o-1))%MOD;
        o=D[i];
        pp%=MOD;
    }
    if(flag==0){
        pp*=lll;
        pp%=MOD;
    }
    pp=pp%MOD;
    return pp;
}

Subtask #1
5.0 / 5.0

#	결과	메모리	Grader output
1	Correct	6360 KB	Output is correct
2	Correct	6360 KB	Output is correct
3	Correct	6360 KB	Output is correct
4	Correct	6360 KB	Output is correct
5	Correct	6360 KB	Output is correct

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	6360 KB	Output is correct
2	Correct	0 ms	6360 KB	Output is correct
3	Correct	0 ms	6360 KB	Output is correct
4	Correct	0 ms	6360 KB	Output is correct
5	Correct	0 ms	6360 KB	Output is correct
6	Correct	11 ms	6360 KB	Output is correct
7	Correct	26 ms	6360 KB	Output is correct
8	Correct	14 ms	6360 KB	Output is correct
9	Correct	6 ms	6360 KB	Output is correct
10	Correct	19 ms	6360 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	6360 KB	Output is correct
2	Correct	0 ms	6360 KB	Output is correct
3	Correct	0 ms	6360 KB	Output is correct
4	Correct	0 ms	6360 KB	Output is correct
5	Correct	0 ms	6360 KB	Output is correct
6	Correct	9 ms	6360 KB	Output is correct
7	Correct	23 ms	6360 KB	Output is correct
8	Correct	17 ms	6360 KB	Output is correct
9	Correct	0 ms	6360 KB	Output is correct
10	Correct	18 ms	6360 KB	Output is correct
11	Correct	0 ms	6360 KB	Output is correct
12	Correct	0 ms	6360 KB	Output is correct
13	Correct	11 ms	6360 KB	Output is correct
14	Correct	0 ms	6360 KB	Output is correct
15	Correct	24 ms	6360 KB	Output is correct

Subtask #4
5.0 / 5.0

#	결과	메모리	Grader output
1	Correct	6360 KB	Output is correct
2	Correct	6360 KB	Output is correct
3	Correct	6360 KB	Output is correct
4	Correct	6360 KB	Output is correct
5	Correct	6360 KB	Output is correct

Subtask #5
10.0 / 10.0

#	결과	메모리	Grader output
1	Correct	6360 KB	Output is correct
2	Correct	6360 KB	Output is correct
3	Correct	6360 KB	Output is correct
4	Correct	6360 KB	Output is correct
5	Correct	6360 KB	Output is correct
6	Correct	6360 KB	Output is correct
7	Correct	6360 KB	Output is correct
8	Correct	6360 KB	Output is correct
9	Correct	6360 KB	Output is correct
10	Correct	6360 KB	Output is correct

Subtask #6
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	6360 KB	Output is correct
2	Correct	0 ms	6360 KB	Output is correct
3	Correct	0 ms	6360 KB	Output is correct
4	Correct	0 ms	6360 KB	Output is correct
5	Correct	0 ms	6360 KB	Output is correct
6	Correct	0 ms	6360 KB	Output is correct
7	Correct	0 ms	6360 KB	Output is correct
8	Correct	0 ms	6360 KB	Output is correct
9	Correct	0 ms	6360 KB	Output is correct
10	Correct	0 ms	6360 KB	Output is correct
11	Correct	12 ms	6360 KB	Output is correct
12	Correct	21 ms	6360 KB	Output is correct
13	Correct	17 ms	6360 KB	Output is correct
14	Correct	16 ms	6360 KB	Output is correct
15	Correct	35 ms	6360 KB	Output is correct

Subtask #7
5.0 / 5.0

#	결과	메모리	Grader output
1	Correct	6360 KB	Output is correct
2	Correct	6360 KB	Output is correct
3	Correct	6360 KB	Output is correct

Subtask #8
15.0 / 15.0

#	결과	메모리	Grader output
1	Correct	6360 KB	Output is correct
2	Correct	6360 KB	Output is correct
3	Correct	6360 KB	Output is correct
4	Correct	6360 KB	Output is correct
5	Correct	6360 KB	Output is correct
6	Correct	6360 KB	Output is correct
7	Correct	6360 KB	Output is correct
8	Correct	6360 KB	Output is correct

Subtask #9
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	6360 KB	Output is correct
2	Correct	0 ms	6360 KB	Output is correct
3	Correct	0 ms	6360 KB	Output is correct
4	Correct	0 ms	6360 KB	Output is correct
5	Correct	0 ms	6360 KB	Output is correct
6	Correct	0 ms	6360 KB	Output is correct
7	Correct	0 ms	6360 KB	Output is correct
8	Correct	0 ms	6360 KB	Output is correct
9	Correct	22 ms	6360 KB	Output is correct
10	Correct	23 ms	6360 KB	Output is correct
11	Correct	9 ms	6360 KB	Output is correct
12	Correct	12 ms	6360 KB	Output is correct
13	Correct	4 ms	6360 KB	Output is correct

Subtask #10
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	6360 KB	Output is correct
2	Correct	0 ms	6360 KB	Output is correct
3	Correct	0 ms	6360 KB	Output is correct
4	Correct	0 ms	6360 KB	Output is correct
5	Correct	0 ms	6360 KB	Output is correct
6	Correct	0 ms	6360 KB	Output is correct
7	Correct	0 ms	6360 KB	Output is correct
8	Correct	0 ms	6360 KB	Output is correct
9	Correct	27 ms	6360 KB	Output is correct
10	Correct	29 ms	6360 KB	Output is correct
11	Correct	13 ms	6360 KB	Output is correct
12	Correct	15 ms	6360 KB	Output is correct
13	Correct	4 ms	6360 KB	Output is correct
14	Correct	49 ms	6360 KB	Output is correct
15	Correct	50 ms	6360 KB	Output is correct
16	Correct	7 ms	6360 KB	Output is correct
17	Correct	38 ms	6360 KB	Output is correct
18	Correct	12 ms	6360 KB	Output is correct

답안 #16453

Compilation message