답안 #638392

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
638392	2022-09-05T17:50:07 Z	ggoh	곤돌라 (IOI14_gondola)	C++14	100 / 100	28 ms	3488 KB

gondola

#include<gondola.h>
#include<bits/stdc++.h>
using namespace std;
typedef long long lint;
lint X=1e9+9;
lint po(lint p,int q)
{
  if(q==0)return 1ll;
  if(q==1)return p;
  lint o=po(p,q/2);
  o=o*o%X;
  if(q%2)return o*p%X;
  else return o;
}
int valid(int n, int inputSeq[])
{
  vector<int>check(n+1),copy(n);
  for(int i=0;i<n;i++)
  {
    copy[i]=inputSeq[i];
    if(inputSeq[i]<=n)check[inputSeq[i]]=i+1;
  }
  sort(copy.begin(),copy.end());
  for(int i=0;i<n;i++)if(copy[i]==copy[i+1])return 0;
  int c=0,ans=1,pos,t;
  for(int i=1;i<=n;i++)
  {
    if(check[i])
    {
      if(!c)c=i,pos=check[i];
      else
      {
        t=check[i]-pos;
        if(t<=0)t+=n;
        if(t!=i-c)ans=0;
      }
    }
  }
  return ans;
}
 
 
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
  vector<int>top(n),ans;
  int c=0,pos;
  for(int i=0;i<n;i++)
  {
    if(gondolaSeq[i]<=n)
    {
      c=gondolaSeq[i];
      pos=i;
    }
  }
  int left=0;
  if(c)
  {
    left=pos-(c-1);
  }
  vector<pair<int,int>>newG;
  for(int i=0;i<n;i++)
  {
    top[i]=i+1;
    newG.push_back({gondolaSeq[i],(i+n-left)%n});
  }
  sort(newG.begin(),newG.end());
  int t=n+1;
  for(auto &k:newG)
  {
    if(top[k.second]==k.first)continue;
    ans.push_back(top[k.second]);
    top[k.second]=t;
    t++;
    while(top[k.second]!=k.first)
    {
      ans.push_back(top[k.second]);
      top[k.second]++;
      t++;
    }
  }
  int sz=(int)ans.size();
  for(int i=0;i<sz;i++)replacementSeq[i]=ans[i];
  return sz;
}
 
 
int countReplacement(int n, int inputSeq[])
{
  if(!valid(n,inputSeq))return 0;
  lint ans=1ll,mul;
  vector<int>top(n);
  int c=0,pos;
  for(int i=0;i<n;i++)
  {
    if(inputSeq[i]<=n)
    {
      c=inputSeq[i];
      pos=i;
    }
  }
  int left=0;
  if(c)
  {
    left=pos-(c-1);
  }
  else ans=n;
  vector<pair<int,int>>newG;
  for(int i=0;i<n;i++)
  {
    top[i]=i+1;
    newG.push_back({inputSeq[i],(i+n-left)%n});
  }
  mul=n;
  sort(newG.begin(),newG.end());
  int t=n+1;
  for(auto &k:newG)
  {
    if(k.first==k.second+1)mul--;
    else
    {
      ans*=po(mul,k.first-t);
      ans%=X;
      t=k.first+1;
      mul--;
    }
  }
  return ans;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	6 ms	724 KB	Output is correct
7	Correct	13 ms	1352 KB	Output is correct
8	Correct	12 ms	1076 KB	Output is correct
9	Correct	4 ms	468 KB	Output is correct
10	Correct	12 ms	1300 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	6 ms	724 KB	Output is correct
7	Correct	17 ms	1236 KB	Output is correct
8	Correct	9 ms	1084 KB	Output is correct
9	Correct	4 ms	468 KB	Output is correct
10	Correct	13 ms	1184 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	6 ms	672 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	14 ms	1236 KB	Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	19 ms	1940 KB	Output is correct
10	Correct	15 ms	1588 KB	Output is correct
11	Correct	6 ms	804 KB	Output is correct
12	Correct	7 ms	896 KB	Output is correct
13	Correct	2 ms	468 KB	Output is correct

Subtask #10
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	20 ms	1972 KB	Output is correct
10	Correct	18 ms	1560 KB	Output is correct
11	Correct	6 ms	804 KB	Output is correct
12	Correct	7 ms	896 KB	Output is correct
13	Correct	2 ms	468 KB	Output is correct
14	Correct	25 ms	3244 KB	Output is correct
15	Correct	28 ms	3488 KB	Output is correct
16	Correct	5 ms	972 KB	Output is correct
17	Correct	22 ms	2120 KB	Output is correct
18	Correct	10 ms	1572 KB	Output is correct

답안 #638392

Compilation message