답안 #93787 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
93787	2019-01-11T10:51:39 Z	Bodo171	곤돌라 (IOI14_gondola)	C++14	90 / 100	28 ms	4856 KB

gondola

#include "gondola.h"
#include <iostream>
using namespace std;
const int nmax=100005;
const long long mod=1000*1000*1000+9;
int ap[10*nmax];
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;
}

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

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;
  for(int i=1000*1000;i>n;i--)
  {
      if(ap[i])  ap[i]+=ap[i+1];
      else
      {
          ap[i]=ap[i+1];
          f=ap[i];
          if(f)ans=(1LL*ans*f)%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	256 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	6 ms	760 KB	Output is correct
7	Correct	12 ms	1144 KB	Output is correct
8	Correct	10 ms	1144 KB	Output is correct
9	Correct	4 ms	632 KB	Output is correct
10	Correct	12 ms	1272 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	376 KB	Output is correct
4	Correct	2 ms	296 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	6 ms	760 KB	Output is correct
7	Correct	12 ms	1016 KB	Output is correct
8	Correct	10 ms	1144 KB	Output is correct
9	Correct	4 ms	632 KB	Output is correct
10	Correct	12 ms	1272 KB	Output is correct
11	Correct	2 ms	376 KB	Output is correct
12	Correct	2 ms	376 KB	Output is correct
13	Correct	7 ms	888 KB	Output is correct
14	Correct	2 ms	376 KB	Output is correct
15	Correct	13 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	316 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	292 KB	Output is correct

Subtask #5
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	420 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	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	2 ms	376 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	420 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	380 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	2 ms	420 KB	Output is correct
11	Correct	10 ms	1200 KB	Output is correct
12	Correct	12 ms	1400 KB	Output is correct
13	Correct	13 ms	1784 KB	Output is correct
14	Correct	10 ms	1272 KB	Output is correct
15	Correct	19 ms	2680 KB	Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	4216 KB	Output is correct
2	Correct	7 ms	4216 KB	Output is correct
3	Correct	8 ms	4216 KB	Output is correct
4	Correct	7 ms	4216 KB	Output is correct
5	Correct	7 ms	4216 KB	Output is correct
6	Correct	7 ms	4216 KB	Output is correct
7	Correct	8 ms	4188 KB	Output is correct
8	Correct	8 ms	4216 KB	Output is correct
9	Correct	18 ms	4856 KB	Output is correct
10	Correct	16 ms	4728 KB	Output is correct
11	Correct	11 ms	4344 KB	Output is correct
12	Correct	12 ms	4448 KB	Output is correct
13	Correct	10 ms	4232 KB	Output is correct

Subtask #10
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	4216 KB	Output is correct
2	Correct	8 ms	4216 KB	Output is correct
3	Correct	8 ms	4216 KB	Output is correct
4	Correct	8 ms	4216 KB	Output is correct
5	Correct	7 ms	4216 KB	Output is correct
6	Correct	7 ms	4216 KB	Output is correct
7	Correct	8 ms	4268 KB	Output is correct
8	Correct	7 ms	4264 KB	Output is correct
9	Correct	17 ms	4856 KB	Output is correct
10	Correct	28 ms	4728 KB	Output is correct
11	Correct	11 ms	4344 KB	Output is correct
12	Correct	11 ms	4472 KB	Output is correct
13	Correct	8 ms	4216 KB	Output is correct
14	Runtime error	16 ms	2652 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
15	Halted	0 ms	0 KB	-

답안 #93787

Compilation message