oj.uz

Submission #66376

# Submission time Handle Problem Language Result Execution time Memory
66376 2018-08-10T10:46:49 Z someone_aa Gondola (IOI14_gondola) C++17
60 / 100
 81 ms 10412 KB 
#include "gondola.h"
#include <bits/stdc++.h>

#define ll long long
using namespace std;
const int maxn = 250100;
const ll mod = 1000000009;
map<int, bool>exist;
int fin_val[maxn];
ll cnt[maxn];

int valid(int n, int arr[]) {
    bool check = true;

    for(int i=1;i<n;i++) {
        if(arr[i] > n) continue;
        else if(arr[i] == 1) {
            if(arr[i-1] < n)
                check = false;
        }
        else {
            if(arr[i-1] <= n && arr[i-1] != arr[i] - 1) check = false;
        }
    }

    sort(arr, arr+n);
    for(int i=1;i<n;i++) {
        if(arr[i] == arr[i-1]) check = false;
    }
    if(check) return 1;
    else return 0;
}

//----------------------

int replacement(int n, int arr[], int replacementSeq[]) {
    int maxm = 0;
    int found_i = 0, st_val = 1;
    for(int i=0;i<n;i++) {
        exist[arr[i]] = true;
        if(arr[i] <= n) {
            found_i = i;
            st_val = arr[i];
        }
        maxm = max(maxm, arr[i]);
    }
    exist[n] = true;
    int l = maxm - n;


    for(int i=found_i;i<n;i++) {
        fin_val[i] = st_val;
        st_val++;
        if(st_val == n + 1) st_val = 1;
    }

    for(int i=0;i<found_i;i++) {
        fin_val[i] = st_val;
        st_val++;
        if(st_val == n + 1) st_val = 1;
    }

    for(int i=0;i<n;i++) {
        while(!exist[arr[i]-1] && arr[i] > n) {
            replacementSeq[arr[i]-n-1] = arr[i] - 1;
            arr[i]--;
        }
        if(arr[i] > n) replacementSeq[arr[i]-n-1] = fin_val[i];
    }

    return l;
}

//----------------------

ll power(ll a, ll b) {
    if(b == 0) return 1LL;
    else if(b == 1) return 1LL * a % mod;
    else {
        if(b%2 == 0) {
            ll half = power(a, b/2) % mod;
            return (1LL*half * half)% mod;
        }
        else if(b%2==1) {
            return (power(a, b-1)) % mod;
        }
    }
}

int countReplacement(int n, int arr[]) {
    if(!valid(n, arr)) return 0;
    vector<ll>nums;
    for(int i=0;i<n;i++) {
        if(arr[i] > n) nums.push_back(arr[i]);
    }
    nums.push_back(n);
    sort(nums.begin(), nums.end());

    ll result = 1LL;
    for(int i=1;i<nums.size();i++) {
        ll diff = 1LL * nums[i] - nums[i-1] - 1;
        ll p = 1LL * int(nums.size()) - i;
        result *= 1LL*power(p, diff);
        result %= mod;
    }

    if(nums.size() > n) {
        result *= n;
        result %= mod;
    }
    return result;
}

/*int main() {
    int arr[] = {2, 3, 4, 9, 6, 7, 12};
    int arr2[1];
    cout<<countReplacement(7, arr);
}*/

Compilation message

gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:100:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1;i<nums.size();i++) {
                 ~^~~~~~~~~~~~
gondola.cpp:107:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(nums.size() > n) {
        ~~~~~~~~~~~~^~~
gondola.cpp: In function 'long long int power(long long int, long long int)':
gondola.cpp:88:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 3 ms 356 KB Output is correct
3 Correct 3 ms 392 KB Output is correct
4 Correct 3 ms 392 KB Output is correct
5 Correct 3 ms 468 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 644 KB Output is correct
3 Correct 2 ms 644 KB Output is correct
4 Correct 2 ms 644 KB Output is correct
5 Correct 2 ms 644 KB Output is correct
6 Correct 15 ms 748 KB Output is correct
7 Correct 23 ms 880 KB Output is correct
8 Correct 15 ms 880 KB Output is correct
9 Correct 8 ms 880 KB Output is correct
10 Correct 20 ms 880 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 880 KB Output is correct
2 Correct 3 ms 880 KB Output is correct
3 Correct 2 ms 880 KB Output is correct
4 Correct 2 ms 880 KB Output is correct
5 Correct 2 ms 880 KB Output is correct
6 Correct 12 ms 880 KB Output is correct
7 Correct 23 ms 880 KB Output is correct
8 Correct 14 ms 912 KB Output is correct
9 Correct 8 ms 912 KB Output is correct
10 Correct 24 ms 924 KB Output is correct
11 Correct 2 ms 924 KB Output is correct
12 Correct 2 ms 924 KB Output is correct
13 Correct 14 ms 924 KB Output is correct
14 Correct 2 ms 924 KB Output is correct
15 Correct 24 ms 924 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 924 KB Output is correct
2 Correct 2 ms 924 KB Output is correct
3 Correct 2 ms 924 KB Output is correct
4 Correct 2 ms 924 KB Output is correct
5 Correct 2 ms 924 KB Output is correct
6 Correct 2 ms 924 KB Output is correct
7 Correct 3 ms 924 KB Output is correct
8 Correct 3 ms 924 KB Output is correct
9 Correct 3 ms 924 KB Output is correct
10 Correct 4 ms 940 KB Output is correct
11 Correct 39 ms 4900 KB Output is correct
12 Correct 50 ms 5548 KB Output is correct
13 Correct 62 ms 5548 KB Output is correct
14 Correct 48 ms 5548 KB Output is correct
15 Correct 81 ms 10412 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10412 KB Output is correct
2 Correct 3 ms 10412 KB Output is correct
3 Correct 3 ms 10412 KB Output is correct
4 Correct 2 ms 10412 KB Output is correct
5 Incorrect 2 ms 10412 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10412 KB Output is correct
2 Correct 2 ms 10412 KB Output is correct
3 Correct 2 ms 10412 KB Output is correct
4 Correct 2 ms 10412 KB Output is correct
5 Incorrect 2 ms 10412 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10412 KB Output is correct
2 Correct 2 ms 10412 KB Output is correct
3 Correct 2 ms 10412 KB Output is correct
4 Correct 2 ms 10412 KB Output is correct
5 Incorrect 2 ms 10412 KB Output isn't correct
6 Halted 0 ms 0 KB -