oj.uz

Submission #57593

# Submission time Handle Problem Language Result Execution time Memory
57593 2018-07-15T11:40:26 Z vex Gondola (IOI14_gondola) C++14
75 / 100
 74 ms 3252 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -