oj.uz

Submission #58841

# Submission time Handle Problem Language Result Execution time Memory
58841 2018-07-19T15:50:17 Z muradeyn Gondola (IOI14_gondola) C++14
60 / 100
 53 ms 8208 KB 
#include "gondola.h"
#include <bits/stdc++.h>
#define MOD 1000000009LL

long long powmod(int a,int b) {
    if (b == 0)return 1;
    if (b == 1)return a;
    long long lilhelp = powmod(a,b/2);
    long long ret = (lilhelp * lilhelp) % MOD;
    if (b % 2 == 1) ret = (ret * a) % MOD;
    return ret;
}

int valid(int n, int inputSeq[])
{
    std::set<int>st;
    int ls = -1,in;
    for (int i = 0;i<n;i++) {
        st.insert(inputSeq[i]);
        if (inputSeq[i] <= n) {
            if (ls == -1) {
                in = i;
                ls = inputSeq[i];
                continue;
            }
            if (inputSeq[i] < ls) {
                if (inputSeq[i] != 1)return 0;
                else if (ls - inputSeq[i] != n - i + in)return 0;
            }
            else {
                if (inputSeq[i] - ls != i - in)return 0;
            }
            in = i;
            ls = inputSeq[i];
        }
    }
    if (st.size() != n)return 0;
    return 1;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
    int in[n],le = 0,idx = -1 , sz = 0;
    std::vector< std::pair<int,int> >v;
    for (int i = 0;i<n;i++) in[i] = i + 1;
    for (int i = 0;i<n;i++) {
        if (gondolaSeq[i] <= n) {
            idx = i;
            in[i] = gondolaSeq[i];
        }
        else {
            v.push_back(std::make_pair(gondolaSeq[i],i));
            sz++;
        }
    }
    std::sort(v.begin(),v.end());
    if (idx != -1) {
        int l = idx - 1,r = idx + 1;
        while (l >= 0) {
            if (in[l + 1] == 1)in[l] = n;
            else in[l] = in[l + 1] - 1;
            l--;
        }
        while (r < n) {
            if (in[r - 1] == n)in[r] = 1;
            else in[r] = in[r - 1] + 1;
            r++;
        }
    }
    for (int i = 0;i<sz;i++) {
        if (i == 0) {
            replacementSeq[le++] = in[v[i].second];
            int k = n + 1;
            while (k < v[i].first) {
                replacementSeq[le++] = k;
                k++;
            }
        }
        else {
            replacementSeq[le++] = in[v[i].second];
            int k = v[i - 1].first + 1;
            while (k < v[i].first) {
                replacementSeq[le++] = k;
                k++;
            }
        }
        /*std::cout<<i<<" "<<le<<std::endl;
        for (int j = 0;j<le;j++) std::cout<<replacementSeq[j]<<" ";
        std::cout<<std::endl;*/
    }
    return le;
}

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

int countReplacement(int n, int inputSeq[])
{
    if (valid(n,inputSeq) == 0)return 0;
    long long mx = -1;
    long long int ans = 1 , lft = 0 , sz = 0,lst;
    std::vector< std::pair<long long int,long long int> >v;
    for (int i = 0;i<n;i++) {
        mx = std::max(mx,inputSeq[i]*1LL);
        if (inputSeq[i] > n) {
            v.push_back(std::make_pair(inputSeq[i],i));
            sz++;
            lft++;
        }
    }
    std::sort(v.begin(),v.end());
    lst = n;
    for (int i = 0;i<sz;i++) {
        ans = (ans * powmod(lft,v[i].first - lst - 1)) % MOD;
        lft--;
        lst = v[i].first;
    }
    if (sz == n)ans *= n;
    if (sz == n && mx == n  *2)return 1;
    return ans % MOD;
}

Compilation message

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:37:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (st.size() != n)return 0;
         ~~~~~~~~~~^~~~
gondola.cpp:28:52: warning: 'in' may be used uninitialized in this function [-Wmaybe-uninitialized]
                 else if (ls - inputSeq[i] != n - i + in)return 0;
                                              ~~~~~~^~~~

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 3 ms 484 KB Output is correct
4 Correct 3 ms 484 KB Output is correct
5 Correct 3 ms 484 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 544 KB Output is correct
2 Correct 2 ms 592 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 3 ms 612 KB Output is correct
5 Correct 3 ms 612 KB Output is correct
6 Correct 17 ms 2532 KB Output is correct
7 Correct 16 ms 2532 KB Output is correct
8 Correct 29 ms 5120 KB Output is correct
9 Correct 15 ms 5120 KB Output is correct
10 Correct 38 ms 6164 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6164 KB Output is correct
2 Correct 2 ms 6164 KB Output is correct
3 Correct 2 ms 6164 KB Output is correct
4 Correct 3 ms 6164 KB Output is correct
5 Correct 2 ms 6164 KB Output is correct
6 Correct 21 ms 6164 KB Output is correct
7 Correct 19 ms 6164 KB Output is correct
8 Correct 39 ms 6632 KB Output is correct
9 Correct 12 ms 6632 KB Output is correct
10 Correct 53 ms 7804 KB Output is correct
11 Correct 4 ms 7804 KB Output is correct
12 Correct 3 ms 7804 KB Output is correct
13 Correct 11 ms 7804 KB Output is correct
14 Correct 3 ms 7804 KB Output is correct
15 Correct 22 ms 7804 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7804 KB Output is correct
2 Correct 3 ms 7804 KB Output is correct
3 Correct 2 ms 7804 KB Output is correct
4 Correct 3 ms 7804 KB Output is correct
5 Correct 2 ms 7804 KB Output is correct
6 Correct 2 ms 7804 KB Output is correct
7 Correct 3 ms 7804 KB Output is correct
8 Correct 3 ms 7804 KB Output is correct
9 Correct 5 ms 7804 KB Output is correct
10 Correct 3 ms 7804 KB Output is correct
11 Correct 17 ms 7804 KB Output is correct
12 Correct 18 ms 7804 KB Output is correct
13 Correct 24 ms 7804 KB Output is correct
14 Correct 14 ms 7804 KB Output is correct
15 Correct 31 ms 8208 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8208 KB Output is correct
2 Correct 3 ms 8208 KB Output is correct
3 Correct 3 ms 8208 KB Output is correct
4 Correct 2 ms 8208 KB Output is correct
5 Incorrect 2 ms 8208 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 8208 KB Output is correct
2 Correct 2 ms 8208 KB Output is correct
3 Correct 2 ms 8208 KB Output is correct
4 Correct 3 ms 8208 KB Output is correct
5 Incorrect 3 ms 8208 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

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