oj.uz

Submission #70116

# Submission time Handle Problem Language Result Execution time Memory
70116 2018-08-22T11:22:10 Z zubec Gondola (IOI14_gondola) C++14
100 / 100
 159 ms 16868 KB 
#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 100100;
const ll MOD = 1e9+9;

int a[N], b[N];
ll fact[N];


int valid(int n, int inputSeq[]){

    map<int, int> mp1;
    map<int, int> used, used2;
    for (int i = 1; i <= n; i++){
        a[i] = inputSeq[i-1];
        if (a[i] > n){
            if (++mp1[a[i]] > 1)
                return 0;
        }
    }
    a[n+1] = a[1];
    int prev = 0;
    for (int i = 1; i <= n; i++){
        if (used.find(a[i+1]) != used.end())
            a[i+1] = used[a[i+1]];
        if (a[i] > n)
            continue;
        if (a[i+1] > n){
            if (a[i] == n){
                if (used2.find(1) != used2.end())
                    return 0;
                used[a[i+1]] = 1;
                used2[1] = a[i+1];
                a[i+1] = 1;
            } else {
                if (used2.find(a[i]+1) != used2.end())
                    return 0;
                used[a[i+1]] = a[i]+1;
                used2[a[i]+1] = a[i+1];
                a[i+1] = a[i]+1;
            }
        } else {
            if (a[i] == n){
                if (a[i+1] != 1)
                    return 0;
            } else {
                if (a[i+1] != a[i] + 1)
                    return 0;
            }
        }
    }

    return 1;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[]){
    vector <pair<int, int> > vec;
    for (int i = 1; i <= n; i++){
        a[i] = gondolaSeq[i-1];
        if (a[i] > n){
            vec.push_back({a[i], i});
        }
    }
    a[n+1] = a[1];

    for (int i = 1; i <= n; i++){
        if (a[i] <= n){
            if (a[i] == n)
                a[i+1] = 1; else
                a[i+1] = a[i] + 1;
        }
    }
    for (int i = n+1; i > 1; i--){
        if (a[i] <= n){
            if (a[i] == 1)
                a[i-1] = n; else
                a[i-1] = a[i] - 1;
        }
    }
    if (a[1] > n){
        for (int i = 1; i <= n; i++)
            a[i] = i;
    }

    int cnt = 0;
    int curnumb = n+1;
    sort(vec.begin(), vec.end());
    for (int i = 0; i < vec.size(); i++){
        int cur = a[vec[i].second];
        while(cur != vec[i].first){
            replacementSeq[cnt++] = cur;
            cur = curnumb;
            ++curnumb;
        }
    }
    return cnt;


}

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

ll binpow(ll a, ll b){
    ll res = 1;
    while(b){
        if (b & 1){
            res = (res * a) % MOD;
        }
        a = (a * a) % MOD;
        b>>=1;
    }
    return res;
}

int countReplacement(int n, int inputSeq[]){

    if (valid(n, inputSeq) == 0)
        return 0;
    fact[0] = 1;
    for (int i = 1; i <= n; i++)
        fact[i] = (fact[i-1] * 1ll * i) % MOD;
    int cnt = 0;
    vector <pair<int, int> > vec;
    for (int i = 1; i <= n; i++){
        a[i] = inputSeq[i-1];
        if (a[i] > n){
            vec.push_back({a[i], i});
            ++cnt;
        }
    }
    a[n+1] = a[1];

    for (int i = 1; i <= n; i++){
        if (a[i] <= n){
            if (a[i] == n)
                a[i+1] = 1; else
                a[i+1] = a[i] + 1;
        }
    }
    for (int i = n+1; i > 1; i--){
        if (a[i] <= n){
            if (a[i] == 1)
                a[i-1] = n; else
                a[i-1] = a[i] - 1;
        }
    }
    ll ans = 1;
    if (a[1] > n)
        ans = n;
    int lst = n+1;
    sort(vec.begin(), vec.end());
    for (int i = 0; i < vec.size(); i++){
        ans = (ans * binpow(cnt-i, vec[i].first-lst)) % MOD;
        lst = vec[i].first+1;
    }


    return ans;

}

Compilation message

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:25:9: warning: unused variable 'prev' [-Wunused-variable]
     int prev = 0;
         ^~~~
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:93:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < vec.size(); i++){
                     ~~^~~~~~~~~~~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:157:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < vec.size(); i++){
                     ~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 584 KB Output is correct
2 Correct 5 ms 584 KB Output is correct
3 Correct 3 ms 584 KB Output is correct
4 Correct 2 ms 584 KB Output is correct
5 Correct 3 ms 584 KB Output is correct
6 Correct 8 ms 968 KB Output is correct
7 Correct 21 ms 1948 KB Output is correct
8 Correct 24 ms 2196 KB Output is correct
9 Correct 6 ms 2196 KB Output is correct
10 Correct 20 ms 3032 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3032 KB Output is correct
2 Correct 2 ms 3032 KB Output is correct
3 Correct 2 ms 3032 KB Output is correct
4 Correct 3 ms 3032 KB Output is correct
5 Correct 3 ms 3032 KB Output is correct
6 Correct 9 ms 3032 KB Output is correct
7 Correct 20 ms 4004 KB Output is correct
8 Correct 16 ms 4004 KB Output is correct
9 Correct 7 ms 4004 KB Output is correct
10 Correct 17 ms 4656 KB Output is correct
11 Correct 2 ms 4656 KB Output is correct
12 Correct 2 ms 4656 KB Output is correct
13 Correct 30 ms 5896 KB Output is correct
14 Correct 2 ms 5896 KB Output is correct
15 Correct 39 ms 5896 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5896 KB Output is correct
2 Correct 3 ms 5896 KB Output is correct
3 Correct 4 ms 5896 KB Output is correct
4 Correct 2 ms 5896 KB Output is correct
5 Correct 3 ms 5896 KB Output is correct
6 Correct 3 ms 5896 KB Output is correct
7 Correct 4 ms 5896 KB Output is correct
8 Correct 3 ms 5896 KB Output is correct
9 Correct 3 ms 5896 KB Output is correct
10 Correct 4 ms 5896 KB Output is correct
11 Correct 15 ms 5896 KB Output is correct
12 Correct 17 ms 5896 KB Output is correct
13 Correct 22 ms 6340 KB Output is correct
14 Correct 19 ms 6400 KB Output is correct
15 Correct 28 ms 7808 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7808 KB Output is correct
2 Correct 3 ms 7808 KB Output is correct
3 Correct 3 ms 7808 KB Output is correct
4 Correct 2 ms 7808 KB Output is correct
5 Correct 3 ms 7808 KB Output is correct
6 Correct 3 ms 7808 KB Output is correct
7 Correct 3 ms 7808 KB Output is correct
8 Correct 4 ms 7808 KB Output is correct
9 Correct 131 ms 15580 KB Output is correct
10 Correct 124 ms 15580 KB Output is correct
11 Correct 54 ms 15580 KB Output is correct
12 Correct 58 ms 15580 KB Output is correct
13 Correct 8 ms 15580 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 15580 KB Output is correct
2 Correct 3 ms 15580 KB Output is correct
3 Correct 2 ms 15580 KB Output is correct
4 Correct 2 ms 15580 KB Output is correct
5 Correct 4 ms 15580 KB Output is correct
6 Correct 3 ms 15580 KB Output is correct
7 Correct 3 ms 15580 KB Output is correct
8 Correct 3 ms 15580 KB Output is correct
9 Correct 159 ms 16868 KB Output is correct
10 Correct 123 ms 16868 KB Output is correct
11 Correct 46 ms 16868 KB Output is correct
12 Correct 65 ms 16868 KB Output is correct
13 Correct 7 ms 16868 KB Output is correct
14 Correct 112 ms 16868 KB Output is correct
15 Correct 133 ms 16868 KB Output is correct
16 Correct 16 ms 16868 KB Output is correct
17 Correct 80 ms 16868 KB Output is correct
18 Correct 42 ms 16868 KB Output is correct