oj.uz

Submission #57592

# Submission time Handle Problem Language Result Execution time Memory
57592 2018-07-15T11:32:42 Z vex Gondola (IOI14_gondola) C++14
65 / 100
 32 ms 3812 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];
    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

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

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

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

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

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

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

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

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

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

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