답안 #57593 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
57593	2018-07-15T11:40:26 Z	vex	곤돌라 (IOI14_gondola)	C++14	75 / 100	74 ms	3252 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;
    }
    return sol;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	636 KB	Output is correct
2	Correct	2 ms	636 KB	Output is correct
3	Correct	2 ms	636 KB	Output is correct
4	Correct	3 ms	636 KB	Output is correct
5	Correct	2 ms	636 KB	Output is correct
6	Correct	18 ms	844 KB	Output is correct
7	Correct	21 ms	1228 KB	Output is correct
8	Correct	17 ms	1228 KB	Output is correct
9	Correct	9 ms	1228 KB	Output is correct
10	Correct	25 ms	1236 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	1236 KB	Output is correct
2	Correct	3 ms	1236 KB	Output is correct
3	Correct	3 ms	1236 KB	Output is correct
4	Correct	3 ms	1236 KB	Output is correct
5	Correct	3 ms	1236 KB	Output is correct
6	Correct	16 ms	1236 KB	Output is correct
7	Correct	24 ms	1276 KB	Output is correct
8	Correct	25 ms	1276 KB	Output is correct
9	Correct	9 ms	1276 KB	Output is correct
10	Correct	24 ms	1276 KB	Output is correct
11	Correct	2 ms	1276 KB	Output is correct
12	Correct	3 ms	1276 KB	Output is correct
13	Correct	14 ms	1276 KB	Output is correct
14	Correct	3 ms	1276 KB	Output is correct
15	Correct	28 ms	1852 KB	Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	1852 KB	Output is correct
2	Correct	2 ms	1852 KB	Output is correct
3	Correct	2 ms	1852 KB	Output is correct
4	Correct	2 ms	1852 KB	Output is correct
5	Correct	2 ms	1852 KB	Output is correct
6	Correct	3 ms	1852 KB	Output is correct
7	Correct	3 ms	1852 KB	Output is correct
8	Correct	4 ms	1852 KB	Output is correct
9	Correct	3 ms	1852 KB	Output is correct
10	Correct	3 ms	1852 KB	Output is correct
11	Correct	28 ms	1852 KB	Output is correct
12	Correct	34 ms	1852 KB	Output is correct
13	Correct	24 ms	2484 KB	Output is correct
14	Correct	16 ms	2484 KB	Output is correct
15	Correct	31 ms	3252 KB	Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
0 / 15.0

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

Subtask #10
0 / 10.0

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

답안 #57593

Compilation message