답안 #93790 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
93790	2019-01-11T11:02:06 Z	Bodo171	곤돌라 (IOI14_gondola)	C++14	100 / 100	101 ms	10892 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=1;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*expo(f,inputSeq[0]-n-1))%mod;
      f=n;
      ans=(1LL*ans*f)%mod;
  }
  return ans;
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	380 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	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	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	17 ms	2396 KB	Output is correct
7	Correct	11 ms	1016 KB	Output is correct
8	Correct	36 ms	4216 KB	Output is correct
9	Correct	11 ms	1528 KB	Output is correct
10	Correct	41 ms	4860 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	376 KB	Output is correct
3	Correct	2 ms	256 KB	Output is correct
4	Correct	2 ms	376 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	1072 KB	Output is correct
8	Correct	33 ms	4216 KB	Output is correct
9	Correct	10 ms	1528 KB	Output is correct
10	Correct	39 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	256 KB	Output is correct
15	Correct	11 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	376 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	376 KB	Output is correct
2	Correct	2 ms	256 KB	Output is correct
3	Correct	2 ms	292 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	256 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

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	604 KB	Output is correct
9	Correct	3 ms	576 KB	Output is correct
10	Correct	3 ms	632 KB	Output is correct
11	Correct	31 ms	4728 KB	Output is correct
12	Correct	34 ms	5240 KB	Output is correct
13	Correct	40 ms	4856 KB	Output is correct
14	Correct	29 ms	4600 KB	Output is correct
15	Correct	62 ms	10232 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	252 KB	Output is correct
3	Correct	2 ms	256 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	376 KB	Output is correct
3	Correct	2 ms	256 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

Subtask #9
15.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	256 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	256 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	380 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	65 ms	7036 KB	Output is correct
10	Correct	54 ms	5724 KB	Output is correct
11	Correct	22 ms	2680 KB	Output is correct
12	Correct	28 ms	3064 KB	Output is correct
13	Correct	7 ms	1016 KB	Output is correct

Subtask #10
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	292 KB	Output is correct
2	Correct	3 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	256 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	252 KB	Output is correct
8	Correct	2 ms	256 KB	Output is correct
9	Correct	68 ms	7092 KB	Output is correct
10	Correct	50 ms	5624 KB	Output is correct
11	Correct	20 ms	2552 KB	Output is correct
12	Correct	25 ms	3116 KB	Output is correct
13	Correct	7 ms	1016 KB	Output is correct
14	Correct	90 ms	8908 KB	Output is correct
15	Correct	101 ms	10892 KB	Output is correct
16	Correct	16 ms	2296 KB	Output is correct
17	Correct	69 ms	7416 KB	Output is correct
18	Correct	39 ms	4344 KB	Output is correct

답안 #93790

Compilation message