Submission #589586

#	Time	Username	Problem	Language	Result	Execution time	Memory
589586		AlperenT	Gondola (IOI14_gondola)	C++17	100 / 100	30 ms	6092 KiB

gondola

#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 (stderr)

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 / 5
• Subtask 2: 5 / 5
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 20 / 20
• Subtask 7: 5 / 5
• Subtask 8: 15 / 15
• Subtask 9: 15 / 15
• Subtask 10: 10 / 10