답안 #16440 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
16440	2015-08-25T03:47:35 Z	atomzeno	곤돌라 (IOI14_gondola)	C++	75 / 100	37 ms	7336 KB

gondola

#include "gondola.h"
#define MOD 1000000009
#include<algorithm>
using namespace std;
#define MX 250001
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<=250000;i++){
        check[i]=0;
    }
    for(i=0;i<n;i++){
        if(inputSeq[i]<=n){
            cnt=1;
            ind=(inputSeq[i]-1-i)+n;
            ind%=n;
            break;
        }
    }
    for(i=0;i<n;i++){
        check[inputSeq[i]]++;
        if(check[inputSeq[i]]>=2){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[31];
//----------------------
int calc(int x,int y){//x의 y승
    int i;
    a[0]=x%MOD;
    if(y==0){
        return 1;
    }
    for(i=1;i<=29;i++){
        p=(a[i-1]*a[i-1]);
        a[i]=p%MOD;
    }
    p=1;
    for(i=0;i<=29;i++){
        if((y&(1<<i))!=0){
            p=p*a[i];
            p=p%MOD;
        }
    }
    return p;
}
int countReplacement(int n, int inputSeq[]){
    int o=n,lll=0,i;
    pp=1;
    if(valid(n,inputSeq)==0){return 0;}
    for(i=0;i<n;i++){
        if(inputSeq[i]>n){
            D[lll++]=inputSeq[i];
        }
    }
    sort(D,D+lll);
    for(i=0;i<lll;i++){
        pp*=calc(lll-i,D[i]-o-1);
        o=D[i];
        pp%=MOD;
    }
    return pp;
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	7336 KB	Output is correct
2	Correct	1 ms	7336 KB	Output is correct
3	Correct	0 ms	7336 KB	Output is correct
4	Correct	0 ms	7336 KB	Output is correct
5	Correct	0 ms	7336 KB	Output is correct

Subtask #2
5.0 / 5.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

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

Subtask #7
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	7336 KB	Output is correct
2	Correct	1 ms	7336 KB	Output is correct
3	Correct	0 ms	7336 KB	Output is correct

Subtask #8
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	7336 KB	Output is correct
2	Correct	0 ms	7336 KB	Output is correct
3	Correct	0 ms	7336 KB	Output is correct
4	Correct	1 ms	7336 KB	Output is correct
5	Correct	1 ms	7336 KB	Output is correct
6	Correct	0 ms	7336 KB	Output is correct
7	Correct	0 ms	7336 KB	Output is correct
8	Correct	0 ms	7336 KB	Output is correct

Subtask #9
0.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	7336 KB	Output is correct
2	Correct	0 ms	7336 KB	Output is correct
3	Correct	0 ms	7336 KB	Output is correct
4	Correct	0 ms	7336 KB	Output is correct
5	Correct	0 ms	7336 KB	Output is correct
6	Correct	0 ms	7336 KB	Output is correct
7	Correct	0 ms	7336 KB	Output is correct
8	Correct	0 ms	7336 KB	Output is correct
9	Correct	28 ms	7336 KB	Output is correct
10	Correct	16 ms	7336 KB	Output is correct
11	Correct	10 ms	7336 KB	Output is correct
12	Correct	12 ms	7336 KB	Output is correct
13	Incorrect	0 ms	7336 KB	Output isn't correct

Subtask #10
0.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	7336 KB	Output is correct
2	Correct	0 ms	7336 KB	Output is correct
3	Correct	0 ms	7336 KB	Output is correct
4	Correct	0 ms	7336 KB	Output is correct
5	Correct	0 ms	7336 KB	Output is correct
6	Correct	0 ms	7336 KB	Output is correct
7	Correct	0 ms	7336 KB	Output is correct
8	Correct	0 ms	7336 KB	Output is correct
9	Correct	26 ms	7336 KB	Output is correct
10	Correct	22 ms	7336 KB	Output is correct
11	Correct	10 ms	7336 KB	Output is correct
12	Correct	12 ms	7336 KB	Output is correct
13	Incorrect	4 ms	7336 KB	Output isn't correct
14	Halted	0 ms	0 KB	-

답안 #16440

Compilation message