답안 #57597 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
57597	2018-07-15T11:54:34 Z	vex	곤돌라 (IOI14_gondola)	C++14	100 / 100	48 ms	4368 KB

gondola

#include<bits/stdc++.h>
#include<gondola.h>
#define maxn 250005
#define MOD 1000000009
#define pii pair<int,int>
using namespace std;
 
 
int b[maxn];
int valid(int n, int a[])
{
    int minn=0;
    for(int i=1;i<n;i++)if(a[i]<a[minn])minn=i;
 
    for(int i=0;i<n;i++)b[i]=a[(i+minn)%n];
 
    sort(a,a+n);
    for(int i=0;i<n-1;i++)if(a[i]==a[i+1])return 0;
  	if(b[0]>n)return 1;
 
    int pre=0;
    for(int i=1;i<n;i++)
    {
        if(b[i]<=n)
        {
            if(b[i]-b[pre]!=i-pre)return 0;
            pre=i;
        }
    }
    return 1;
}
 
vector<pii>v;
int replacement(int n, int g[], int r[])
{
    if(!valid(n,g))return -1;
 
    int s=b[0];
    for(int i=0;i<n;i++)if(b[i]>n)
    {
        int br=(s+i)%n;if(br==0)br=n;
        v.push_back({b[i],br});
    }
    sort(v.begin(),v.end());
 
    int len=v.size();
    if(len==0)
    {
        return 0;
    }
 
  	int duz=0;
    for(int i=0;i<len;i++)
    {
        r[duz]=v[i].second;duz++;
        int pre=n;
        if(i!=0)pre=v[i-1].first;
 
        for(int j=pre+1;j<v[i].first;j++)
        {
          r[duz]=j;
          duz++;
        }
    }
  	return v[len-1].first-n;
}
 
long long ste(int x,int y)
{
    if(y==0)return 1;
    if(y%2==1)return (ste(x,y-1)*x)%MOD;
 
    long long res=ste(x,y/2);
    return (res*res)%MOD;
}
 
vector<int>br;
int countReplacement(int n, int a[])
{
    if(!valid(n,a))return 0;
 
    for(int i=0;i<n;i++)if(b[i]>n)br.push_back(b[i]);
    sort(br.begin(),br.end());
 
    long long sol=1;
    int len=br.size();
    for(int i=0;i<len;i++)
    {
        int pre=n;
        if(i!=0)pre=br[i-1];
        sol*=ste(len-i,br[i]-pre-1);
      	sol%=MOD;
    }
  	
  	if(len==n)
    {
        sol*=n;
        sol%=MOD;
    }
  
    return sol;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	544 KB	Output is correct
2	Correct	2 ms	544 KB	Output is correct
3	Correct	3 ms	544 KB	Output is correct
4	Correct	3 ms	544 KB	Output is correct
5	Correct	3 ms	544 KB	Output is correct
6	Correct	16 ms	800 KB	Output is correct
7	Correct	29 ms	1276 KB	Output is correct
8	Correct	18 ms	1276 KB	Output is correct
9	Correct	7 ms	1276 KB	Output is correct
10	Correct	34 ms	1276 KB	Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	1276 KB	Output is correct
2	Correct	2 ms	1276 KB	Output is correct
3	Correct	3 ms	1276 KB	Output is correct
4	Correct	2 ms	1276 KB	Output is correct
5	Correct	2 ms	1276 KB	Output is correct
6	Correct	2 ms	1276 KB	Output is correct
7	Correct	3 ms	1276 KB	Output is correct
8	Correct	3 ms	1276 KB	Output is correct
9	Correct	3 ms	1276 KB	Output is correct
10	Correct	3 ms	1276 KB	Output is correct
11	Correct	18 ms	1276 KB	Output is correct
12	Correct	20 ms	1308 KB	Output is correct
13	Correct	24 ms	1944 KB	Output is correct
14	Correct	15 ms	1944 KB	Output is correct
15	Correct	41 ms	2724 KB	Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

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

Subtask #10
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	2724 KB	Output is correct
2	Correct	3 ms	2724 KB	Output is correct
3	Correct	6 ms	2724 KB	Output is correct
4	Correct	3 ms	2724 KB	Output is correct
5	Correct	4 ms	2724 KB	Output is correct
6	Correct	3 ms	2724 KB	Output is correct
7	Correct	3 ms	2724 KB	Output is correct
8	Correct	2 ms	2724 KB	Output is correct
9	Correct	27 ms	2724 KB	Output is correct
10	Correct	23 ms	2724 KB	Output is correct
11	Correct	13 ms	2724 KB	Output is correct
12	Correct	14 ms	2724 KB	Output is correct
13	Correct	5 ms	2724 KB	Output is correct
14	Correct	43 ms	2764 KB	Output is correct
15	Correct	48 ms	3820 KB	Output is correct
16	Correct	10 ms	3820 KB	Output is correct
17	Correct	36 ms	4188 KB	Output is correct
18	Correct	18 ms	4368 KB	Output is correct

답안 #57597

Compilation message