oj.uz

Submission #589586

# Submission time Handle Problem Language Result Execution time Memory
589586 2022-07-04T21:56:56 Z AlperenT Gondola (IOI14_gondola) C++17
100 / 100
 30 ms 6092 KB 
#include <bits/stdc++.h>
#include "gondola.h"

using namespace std;

const int MOD = 1e9 + 9;

int valid(int n, int arr[]){
    int arr2[n];

    copy(arr, arr + n, arr2);

    sort(arr2, arr2 + n);

    if(unique(arr2, arr2 + n) != arr2 + n) return false;

    int mn = *min_element(arr, arr + n);

    if(mn > n) return true;
    else{
        vector<int> v;

        for(int i = 0; i < n; i++){
            if(arr[i] <= n){
                v.assign(n, 0);

                for(int j = 0; j < n; j++) v[(arr[i] - 1 + (j - i) + n + n) % n] = arr[j];

                break;
            }
        }

        for(int i = 0; i < n; i++) if(v[i] <= n && v[i] != i + 1) return false;

        return true;
    }
}

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

int replacement(int n, int arr[], int ansarr[]){
    vector<int> ans, v;

    int mn = *min_element(arr, arr + n);

    if(mn > n) for(int i = 0; i < n; i++) v.push_back(arr[i]);
    else{
        for(int i = 0; i < n; i++){
            if(arr[i] <= n){
                v.assign(n, 0);

                for(int j = 0; j < n; j++) v[(arr[i] - 1 + (j - i) + n + n) % n] = arr[j];

                break;
            }
        }
    }

    map<int, int> mp;

    for(int i = 0; i < n; i++) mp[v[i]] = i;

    vector<int> curarr(n, 0);

    iota(curarr.begin(), curarr.end(), 1);

    int cur = n + 1;

    for(int i = 0; i < n; i++){
        while(curarr[i] != v[i]){
            if(mp.find(cur) == mp.end()){
                ans.push_back(curarr[i]);
                curarr[i] = cur;
            }
            else{
                ans.push_back(curarr[mp[cur]]);
                curarr[mp[cur]] = cur;
            }

            cur++;
        }
    }

    for(int i = 0; i < ans.size(); i++) ansarr[i] = ans[i];

    return ans.size();
}

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

int binpow(int a, int b){
    int c = 1;

    for(; b > 0; b /= 2, a = (1ll * a * a) % MOD) if(b & 1) c = (1ll * c * a) % MOD;

    return c;
}

int countReplacement(int n, int inputSeq[]){
    if(!valid(n, inputSeq)) return 0;
    else{
        int ans = 1;

        vector<int> vec;

        vec.push_back(n);

        for(int i = 0; i < n; i++) if(inputSeq[i] > n) vec.push_back(inputSeq[i]);

        sort(vec.begin(), vec.end());

        for(int i = 1; i < vec.size(); i++) ans = (1ll * ans * binpow(vec.size() - i, vec[i] - vec[i - 1] - 1)) % MOD;

        if(*min_element(inputSeq, inputSeq + n) > n) ans = (1ll * ans * n) % MOD;

        return ans;
    }
}

Compilation message

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:84:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     for(int i = 0; i < ans.size(); i++) ansarr[i] = ans[i];
      |                    ~~^~~~~~~~~~~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:112:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |         for(int i = 1; i < vec.size(); i++) ans = (1ll * ans * binpow(vec.size() - i, vec[i] - vec[i - 1] - 1)) % MOD;
      |                        ~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 304 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 6 ms 936 KB Output is correct
7 Correct 13 ms 1492 KB Output is correct
8 Correct 10 ms 1472 KB Output is correct
9 Correct 4 ms 580 KB Output is correct
10 Correct 14 ms 1692 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 6 ms 960 KB Output is correct
7 Correct 12 ms 1492 KB Output is correct
8 Correct 9 ms 1512 KB Output is correct
9 Correct 4 ms 596 KB Output is correct
10 Correct 13 ms 1720 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 6 ms 852 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 15 ms 1744 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 308 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 308 KB Output is correct
11 Correct 21 ms 5324 KB Output is correct
12 Correct 24 ms 6092 KB Output is correct
13 Correct 27 ms 3152 KB Output is correct
14 Correct 22 ms 5296 KB Output is correct
15 Correct 30 ms 3184 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 308 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 21 ms 1724 KB Output is correct
10 Correct 13 ms 1508 KB Output is correct
11 Correct 6 ms 852 KB Output is correct
12 Correct 7 ms 864 KB Output is correct
13 Correct 2 ms 340 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 304 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 18 ms 1820 KB Output is correct
10 Correct 15 ms 1488 KB Output is correct
11 Correct 6 ms 780 KB Output is correct
12 Correct 7 ms 832 KB Output is correct
13 Correct 2 ms 340 KB Output is correct
14 Correct 21 ms 2376 KB Output is correct
15 Correct 23 ms 2596 KB Output is correct
16 Correct 4 ms 724 KB Output is correct
17 Correct 16 ms 1724 KB Output is correct
18 Correct 9 ms 1236 KB Output is correct