oj.uz

Submission #70856

# Submission time Handle Problem Language Result Execution time Memory
70856 2018-08-23T14:17:59 Z yusufake Gondola (IOI14_gondola) C++
100 / 100
 129 ms 8612 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 > P[N],mn;
int T[N],j;
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) { j = 0; return 1; }
    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){
    if(valid(n,A) == 0) return 0;
    int i,x,y,z, b=0;
    for(i=0;i<n;i++) P[i] = mp(A[i],i);
    sort(P,P+n);
    y = n+1;
    for(i=0;i<n;i++){
        x = P[i].st;
        if(x <= n) continue;

        z = P[i].nd-j+1;
        if(z <= 0) z += n;
//      cout << j << " " << P[i].nd << " " <<x << " " << z <<  " ss\n";
        B[b++] = z;
        for(; y<x ; y++) B[b++] = y;
        y++;
    }
    return b;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 560 KB Output is correct
2 Correct 4 ms 568 KB Output is correct
3 Correct 3 ms 616 KB Output is correct
4 Correct 3 ms 620 KB Output is correct
5 Correct 4 ms 752 KB Output is correct
6 Correct 23 ms 2820 KB Output is correct
7 Correct 17 ms 2820 KB Output is correct
8 Correct 41 ms 5072 KB Output is correct
9 Correct 14 ms 5072 KB Output is correct
10 Correct 52 ms 5688 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5688 KB Output is correct
2 Correct 2 ms 5688 KB Output is correct
3 Correct 2 ms 5688 KB Output is correct
4 Correct 2 ms 5688 KB Output is correct
5 Correct 2 ms 5688 KB Output is correct
6 Correct 26 ms 5688 KB Output is correct
7 Correct 14 ms 5688 KB Output is correct
8 Correct 38 ms 5688 KB Output is correct
9 Correct 12 ms 5688 KB Output is correct
10 Correct 60 ms 5688 KB Output is correct
11 Correct 3 ms 5688 KB Output is correct
12 Correct 3 ms 5688 KB Output is correct
13 Correct 32 ms 5688 KB Output is correct
14 Correct 2 ms 5688 KB Output is correct
15 Correct 82 ms 5872 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5872 KB Output is correct
2 Correct 2 ms 5872 KB Output is correct
3 Correct 3 ms 5872 KB Output is correct
4 Correct 3 ms 5872 KB Output is correct
5 Correct 2 ms 5872 KB Output is correct
6 Correct 2 ms 5872 KB Output is correct
7 Correct 3 ms 5872 KB Output is correct
8 Correct 3 ms 5872 KB Output is correct
9 Correct 4 ms 5872 KB Output is correct
10 Correct 4 ms 5872 KB Output is correct
11 Correct 51 ms 6628 KB Output is correct
12 Correct 62 ms 7848 KB Output is correct
13 Correct 48 ms 7848 KB Output is correct
14 Correct 58 ms 7848 KB Output is correct
15 Correct 44 ms 7848 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7848 KB Output is correct
2 Correct 2 ms 7848 KB Output is correct
3 Correct 2 ms 7848 KB Output is correct
4 Correct 2 ms 7848 KB Output is correct
5 Correct 3 ms 7848 KB Output is correct
6 Correct 2 ms 7848 KB Output is correct
7 Correct 3 ms 7848 KB Output is correct
8 Correct 3 ms 7848 KB Output is correct
9 Correct 69 ms 7848 KB Output is correct
10 Correct 50 ms 7848 KB Output is correct
11 Correct 21 ms 7848 KB Output is correct
12 Correct 24 ms 7848 KB Output is correct
13 Correct 7 ms 7848 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7848 KB Output is correct
2 Correct 2 ms 7848 KB Output is correct
3 Correct 3 ms 7848 KB Output is correct
4 Correct 3 ms 7848 KB Output is correct
5 Correct 2 ms 7848 KB Output is correct
6 Correct 2 ms 7848 KB Output is correct
7 Correct 3 ms 7848 KB Output is correct
8 Correct 2 ms 7848 KB Output is correct
9 Correct 76 ms 7848 KB Output is correct
10 Correct 62 ms 7848 KB Output is correct
11 Correct 23 ms 7848 KB Output is correct
12 Correct 25 ms 7848 KB Output is correct
13 Correct 6 ms 7848 KB Output is correct
14 Correct 107 ms 7852 KB Output is correct
15 Correct 129 ms 8612 KB Output is correct
16 Correct 16 ms 8612 KB Output is correct
17 Correct 70 ms 8612 KB Output is correct
18 Correct 39 ms 8612 KB Output is correct