답안 #93788 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
93788	2019-01-11T10:58:13 Z	Bodo171	곤돌라 (IOI14_gondola)	C++14	75 / 100	75 ms	10360 KB

gondola

#include "gondola.h"
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
const int nmax=100005;
const long long mod=1000*1000*1000+9;
map<int,int> ap;
int v[nmax];
int i,act;
void permuta(int a[],int b[],int n)
{
    int offset=0;
    for(int i=0;i<n;i++)
        if(a[i]<=n)
            offset=i+1-a[i];
    for(int i=0;i<n;i++)
        b[i]=a[(i+offset+n)%n];
}
int valid(int n, int inputSeq[])
{
  permuta(inputSeq,v,n);
  for(int i=0;i<n;i++)
    {
        if(v[i]<=n&&v[i]!=i+1)
           return 0;
        if(ap[v[i]]) return 0;
        ap[v[i]]=1;
   }

  return 1;
}

//----------------------

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
  int l=0;
  permuta(gondolaSeq,v,n);
  int mx=0;
  for(i=0;i<n;i++)
  {
     ap[v[i]]=i+1;
     mx=max(mx,v[i]);
  }
  act=n;
  for(i=n+1;i<=mx;i++)
    if(ap[i])
  {
     replacementSeq[l++]=ap[i];
     act++;
     while(act<i)
     {
        replacementSeq[l++]=act;
        act++;
     }
  }
  return l;
}

//----------------------
long long expo(long long A,int B)
{
    long long ret=1,p2=A;
    for(int p=0;p<=30;p++)
    {
        if(((1<<p)&B))
             ret=(1LL*ret*p2)%mod;
        p2=(1LL*p2*p2)%mod;
    }
    return ret;
}
int countReplacement(int n, int inputSeq[])
{
    long long f=0,ans=1;
  if(!valid(n,inputSeq)) return 0;
  bool ordered=1;
  for(int i=0;i<n;i++)
    if(ap[i])
      ordered=0;
  sort(inputSeq,inputSeq+n);
  for(i=n-2;i>=0;i--)
    if(inputSeq[i]>n||inputSeq[i+1]>n)
  {
      f=n-1-i;if(inputSeq[i]<n) inputSeq[i]=n;
      ans=(1LL*ans*expo(f,inputSeq[i+1]-inputSeq[i]-1))%mod;
  }
  if(ordered)
  {
      f=n;
      ans=(1LL*ans*f)%mod;
  }
  return ans;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	256 KB	Output is correct
3	Correct	2 ms	256 KB	Output is correct
4	Correct	2 ms	256 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	16 ms	2424 KB	Output is correct
7	Correct	12 ms	1016 KB	Output is correct
8	Correct	34 ms	4220 KB	Output is correct
9	Correct	9 ms	1528 KB	Output is correct
10	Correct	39 ms	4856 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	256 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	256 KB	Output is correct
6	Correct	17 ms	2424 KB	Output is correct
7	Correct	12 ms	1016 KB	Output is correct
8	Correct	36 ms	4348 KB	Output is correct
9	Correct	10 ms	1628 KB	Output is correct
10	Correct	42 ms	4856 KB	Output is correct
11	Correct	2 ms	256 KB	Output is correct
12	Correct	2 ms	376 KB	Output is correct
13	Correct	6 ms	632 KB	Output is correct
14	Correct	2 ms	376 KB	Output is correct
15	Correct	12 ms	1016 KB	Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	256 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	256 KB	Output is correct
4	Correct	2 ms	256 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	256 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	504 KB	Output is correct
9	Correct	2 ms	508 KB	Output is correct
10	Correct	3 ms	632 KB	Output is correct

Subtask #6
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	3 ms	632 KB	Output is correct
9	Correct	3 ms	504 KB	Output is correct
10	Correct	3 ms	632 KB	Output is correct
11	Correct	29 ms	4600 KB	Output is correct
12	Correct	34 ms	5240 KB	Output is correct
13	Correct	39 ms	4856 KB	Output is correct
14	Correct	32 ms	4600 KB	Output is correct
15	Correct	62 ms	10360 KB	Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	380 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	256 KB	Output is correct
9	Correct	72 ms	7032 KB	Output is correct
10	Correct	56 ms	5644 KB	Output is correct
11	Correct	21 ms	2556 KB	Output is correct
12	Correct	26 ms	3064 KB	Output is correct
13	Incorrect	7 ms	1020 KB	Output isn't correct

Subtask #10
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	380 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	75 ms	7160 KB	Output is correct
10	Correct	53 ms	5624 KB	Output is correct
11	Correct	20 ms	2552 KB	Output is correct
12	Correct	26 ms	3064 KB	Output is correct
13	Incorrect	6 ms	1016 KB	Output isn't correct
14	Halted	0 ms	0 KB	-

답안 #93788

Compilation message