oj.uz

Submission #70825

# Submission time Handle Problem Language Result Execution time Memory
70825 2018-08-23T13:48:38 Z yusufake Gondola (IOI14_gondola) C++
65 / 100
 130 ms 14264 KB 
#include <bits/stdc++.h>
using namespace std;
#include "gondola.h"

#define mp make_pair
#define st first
#define nd second
#define ll long long
const int mod = 1e9 + 9;
const int N   = 2e5 + 5;
pair < int , int > mn;
int T[N];
int valid(int n, int *A){
    int i;
    mn = mp(mod,0);
    map < int , int > M;
    M.clear();
    for(i=0;i<n;i++){
        mn = min(mn , mp(A[i],i));
        if(M[ A[i] ]) return 0;
        M[ A[i] ] = 1;
    }
    if(mn.st > n) return 1;
    int j = mn.nd - mn.st+1;
    if(j < 0) j += n;
    for(i=0;i<n;i++)
        if(A[i] <= n && ((j+A[i]-1 < n && j+A[i]-1 != i)||(j+A[i]-1 >= n && j+A[i]-1-n != i)) )
            return 0;
    return 1;
}

ll fast(ll a, ll b){
    ll t=1;
    for(; b ; b>>=1){
        if(b & 1) t = t*a % mod;
        a = a*a % mod;
    }
    return t;
}

int countReplacement(int n, int *A){
    if(valid(n,A) == 0) return 0;
    long long ans=1;
    int i,x,y;
    for(i=0;i<n;i++) T[i] = A[i];
    sort(T,T+n);
    for(i=n-1;i>=0;i--){
        x = T[i];
        if(x <= n) break;
        y = i && T[i-1] > n ? T[i-1] : n;
        ans = ans * fast(n-i,x-y-1) % mod;
    }
    if(i == -1) ans = ans * n % mod;
    return ans;
}

int replacement(int n, int *A, int *B){
    return 0;
    if(valid(n,A) == 0) return 0;
    countReplacement(n,A);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 548 KB Output is correct
4 Correct 3 ms 548 KB Output is correct
5 Correct 2 ms 548 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 548 KB Output is correct
2 Correct 2 ms 580 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 3 ms 724 KB Output is correct
5 Correct 3 ms 724 KB Output is correct
6 Correct 29 ms 2768 KB Output is correct
7 Correct 17 ms 2768 KB Output is correct
8 Correct 40 ms 5464 KB Output is correct
9 Correct 17 ms 5464 KB Output is correct
10 Correct 67 ms 6524 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6524 KB Output is correct
2 Correct 2 ms 6524 KB Output is correct
3 Correct 3 ms 6524 KB Output is correct
4 Correct 3 ms 6524 KB Output is correct
5 Correct 2 ms 6524 KB Output is correct
6 Correct 24 ms 6524 KB Output is correct
7 Correct 20 ms 6524 KB Output is correct
8 Correct 43 ms 7164 KB Output is correct
9 Correct 16 ms 7164 KB Output is correct
10 Correct 53 ms 8428 KB Output is correct
11 Correct 2 ms 8428 KB Output is correct
12 Correct 2 ms 8428 KB Output is correct
13 Correct 31 ms 8428 KB Output is correct
14 Correct 3 ms 8428 KB Output is correct
15 Correct 83 ms 9320 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 9320 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 9320 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 9320 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9320 KB Output is correct
2 Correct 2 ms 9320 KB Output is correct
3 Correct 2 ms 9320 KB Output is correct

Subtask #8
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9320 KB Output is correct
2 Correct 3 ms 9320 KB Output is correct
3 Correct 4 ms 9320 KB Output is correct
4 Correct 3 ms 9320 KB Output is correct
5 Correct 2 ms 9320 KB Output is correct
6 Correct 2 ms 9320 KB Output is correct
7 Correct 2 ms 9320 KB Output is correct
8 Correct 3 ms 9320 KB Output is correct

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9320 KB Output is correct
2 Correct 2 ms 9320 KB Output is correct
3 Correct 3 ms 9320 KB Output is correct
4 Correct 2 ms 9320 KB Output is correct
5 Correct 2 ms 9320 KB Output is correct
6 Correct 3 ms 9320 KB Output is correct
7 Correct 2 ms 9320 KB Output is correct
8 Correct 2 ms 9320 KB Output is correct
9 Correct 61 ms 9420 KB Output is correct
10 Correct 66 ms 9420 KB Output is correct
11 Correct 24 ms 9420 KB Output is correct
12 Correct 26 ms 9420 KB Output is correct
13 Correct 7 ms 9420 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9420 KB Output is correct
2 Correct 3 ms 9420 KB Output is correct
3 Correct 3 ms 9420 KB Output is correct
4 Correct 4 ms 9420 KB Output is correct
5 Correct 2 ms 9420 KB Output is correct
6 Correct 2 ms 9420 KB Output is correct
7 Correct 3 ms 9420 KB Output is correct
8 Correct 2 ms 9420 KB Output is correct
9 Correct 71 ms 10572 KB Output is correct
10 Correct 60 ms 10572 KB Output is correct
11 Correct 23 ms 10572 KB Output is correct
12 Correct 26 ms 10572 KB Output is correct
13 Correct 7 ms 10572 KB Output is correct
14 Correct 130 ms 12812 KB Output is correct
15 Correct 121 ms 14264 KB Output is correct
16 Correct 16 ms 14264 KB Output is correct
17 Correct 76 ms 14264 KB Output is correct
18 Correct 33 ms 14264 KB Output is correct