답안 #7303 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
7303	2014-07-30T06:35:24 Z	gs13068	곤돌라 (IOI14_gondola)	C++	100 / 100	32 ms	4412 KB

gondola

#ifndef __GONDOLA_H__
#define __GONDOLA_H__

#ifdef __cplusplus
extern "C" {
#endif

int valid(int n, int inputSeq[]);

int replacement(int n, int gondolaSeq[], int replacementSeq[]);

int countReplacement(int n, int inputSeq[]);

#ifdef __cplusplus
}
#endif

#endif /* __GONDOLA_H__ */


//#include "gondola.h"
#include <algorithm>

#define MOD 1000000009

int arr[250001];
int now[250001];

int valid(int n, int inputSeq[])
{
  int i,j;
  for(i=0;i<n;i++)if(inputSeq[i]<=n)break;
  if(i<n)for(j=0;j<n;j++)if(inputSeq[j]<=n&&(inputSeq[j]+i)%n!=(inputSeq[i]+j)%n)return 0;
  std::sort(inputSeq,inputSeq+n);
  for(i=1;i<n;i++)if(inputSeq[i-1]==inputSeq[i])return 0;
  return 1;
}

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
  int i,j;
  for(i=1;i<=250000;i++)arr[i]=-1;
  for(i=0;i<n;i++)arr[gondolaSeq[i]]=i;
  for(i=0;i<n;i++)if(gondolaSeq[i]<=n)break;
  for(j=0;j<n;j++)now[j]=i<n?(gondolaSeq[i]+j-i+n-1)%n+1:j+1;
  j=0;
  for(i=0;i<n;i++)if(gondolaSeq[i]>j)j=gondolaSeq[i];
  for(i=n+1;i<=j;i++)
  {
    replacementSeq[i-n-1]=arr[i]>=0?now[arr[i]]:now[arr[j]];
    now[arr[i]>=0?arr[i]:arr[j]]=i;
  }
  return j-n;
}

int f(int x,int y)
{
  if(y==0)return 1;
  if(y&1)return 1LL*x*f(x,y-1)%MOD;
  x=f(x,y>>1);
  return 1LL*x*x%MOD;
}

int countReplacement(int n, int inputSeq[])
{
  if(!valid(n,inputSeq))return 0;
  int i,r=1;
  std::sort(inputSeq,inputSeq+n);
  for(i=0;i<n;i++)
  {
    if(inputSeq[i]<=n)continue;
    r=1LL*r*f(n-i,inputSeq[i]-(i>0?std::max(inputSeq[i-1],n):n)-1)%MOD;
  }
  return 1LL*r*(inputSeq[0]>n?n:1)%MOD;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

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

Subtask #10
10.0 / 10.0

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

답안 #7303

Compilation message