답안 #57592 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
57592	2018-07-15T11:32:42 Z	vex	곤돌라 (IOI14_gondola)	C++14	65 / 100	32 ms	3812 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];
    if(b[0]>n)return 1;
 
    sort(a,a+n);
    for(int i=0;i<n-1;i++)if(a[i]==a[i+1])return 0;
 
    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;
    }
    return sol;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	560 KB	Output is correct
2	Correct	3 ms	560 KB	Output is correct
3	Correct	2 ms	560 KB	Output is correct
4	Correct	3 ms	560 KB	Output is correct
5	Correct	3 ms	560 KB	Output is correct
6	Correct	11 ms	816 KB	Output is correct
7	Correct	27 ms	1200 KB	Output is correct
8	Correct	17 ms	1200 KB	Output is correct
9	Correct	7 ms	1200 KB	Output is correct
10	Correct	21 ms	1248 KB	Output is correct

Subtask #3
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	1248 KB	Output is correct
2	Correct	3 ms	1248 KB	Output is correct
3	Correct	2 ms	1248 KB	Output is correct
4	Correct	2 ms	1248 KB	Output is correct
5	Correct	2 ms	1248 KB	Output is correct
6	Correct	11 ms	1248 KB	Output is correct
7	Correct	23 ms	1256 KB	Output is correct
8	Correct	20 ms	1256 KB	Output is correct
9	Correct	8 ms	1256 KB	Output is correct
10	Correct	26 ms	1260 KB	Output is correct
11	Correct	2 ms	1260 KB	Output is correct
12	Correct	3 ms	1260 KB	Output is correct
13	Correct	12 ms	1260 KB	Output is correct
14	Incorrect	3 ms	1260 KB	Output isn't correct
15	Halted	0 ms	0 KB	-

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	1260 KB	Output is correct
2	Correct	3 ms	1260 KB	Output is correct
3	Correct	2 ms	1260 KB	Output is correct
4	Correct	2 ms	1260 KB	Output is correct
5	Correct	2 ms	1260 KB	Output is correct
6	Correct	3 ms	1260 KB	Output is correct
7	Correct	3 ms	1260 KB	Output is correct
8	Correct	3 ms	1260 KB	Output is correct
9	Correct	2 ms	1260 KB	Output is correct
10	Correct	3 ms	1260 KB	Output is correct
11	Correct	17 ms	1260 KB	Output is correct
12	Correct	29 ms	1308 KB	Output is correct
13	Correct	29 ms	1944 KB	Output is correct
14	Correct	16 ms	1944 KB	Output is correct
15	Correct	32 ms	2712 KB	Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	2712 KB	Output is correct
2	Correct	4 ms	2712 KB	Output is correct
3	Correct	2 ms	2712 KB	Output is correct
4	Correct	3 ms	2712 KB	Output is correct
5	Correct	3 ms	2712 KB	Output is correct
6	Correct	2 ms	2712 KB	Output is correct
7	Correct	3 ms	2712 KB	Output is correct
8	Correct	2 ms	2712 KB	Output is correct
9	Correct	28 ms	2712 KB	Output is correct
10	Correct	22 ms	2712 KB	Output is correct
11	Correct	10 ms	2712 KB	Output is correct
12	Correct	12 ms	2712 KB	Output is correct
13	Incorrect	6 ms	2712 KB	Output isn't correct

Subtask #10
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	2712 KB	Output is correct
2	Correct	4 ms	2712 KB	Output is correct
3	Correct	6 ms	2712 KB	Output is correct
4	Correct	2 ms	2712 KB	Output is correct
5	Correct	2 ms	2712 KB	Output is correct
6	Correct	2 ms	2712 KB	Output is correct
7	Correct	2 ms	2712 KB	Output is correct
8	Correct	3 ms	2712 KB	Output is correct
9	Correct	30 ms	3556 KB	Output is correct
10	Correct	23 ms	3812 KB	Output is correct
11	Correct	12 ms	3812 KB	Output is correct
12	Correct	13 ms	3812 KB	Output is correct
13	Incorrect	6 ms	3812 KB	Output isn't correct
14	Halted	0 ms	0 KB	-

답안 #57592

Compilation message