Submission #195625

#	Time	Username	Problem	Language	Result	Execution time	Memory
195625		jovan_b	Gondola (IOI14_gondola)	C++17	100 / 100	106 ms	10448 KiB

gondola

#include "gondola.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll niz[100005];
ll niz1[100005];
map <ll, bool> bio;

const int MOD = 1000000009;

ll mul(ll a, ll b){
    return (a*b)%MOD;
}

int pw(int a, int b){
    if(b == 0) return 1;
    int res = pw(a, b/2);
    res = mul(res, res);
    if(b%2) res = mul(res, a);
    return res;
}

void shiftuj(int n, int k){
    for(int i=1; i<=n; i++) niz1[i] = niz[i];
    if(k < 0) k += n;
    for(int i=k+1; i<=n; i++){
        niz[i] = niz1[i-k];
    }
    for(int i=1; i<=k; i++){
        niz[i] = niz1[n-k+i];
    }
}

int valid(int n, int inputSeq[]){
    for(int i=1; i<=n; i++){
        niz[i] = inputSeq[i-1];
    }
    for(int i=1; i<=n; i++){
        if(niz[i] <= n){
            shiftuj(n, niz[i]-i);
            break;
        }
    }
    for(int i=1; i<=n; i++){
        if(niz[i] <= n && niz[i] != i) return 0;
        if(bio[niz[i]]) return 0;
        bio[niz[i]] = 1;
    }
    return 1;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[]){
    for(int i=1; i<=n; i++) niz[i] = gondolaSeq[i-1];
    for(int i=1; i<=n; i++){
        if(niz[i] <= n){
            shiftuj(n, niz[i]-i);
            break;
        }
    }
    vector <pair <int, int>> vec;
    for(int i=1; i<=n; i++){
        if(niz[i] != i){
            vec.push_back({niz[i], i});
        }
    }
    sort(vec.begin(), vec.end());
    int prosli = n+1;
    int l = 0;
    for(auto par : vec){
        int a = par.first;
        int b = par.second;
        replacementSeq[l++] = b;
        while(prosli < a){
            replacementSeq[l++] = prosli;
            prosli++;
        }
        prosli++;
    }
    return l;
}

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

int countReplacement(int n, int inputSeq[]){
    if(!valid(n, inputSeq)) return 0;
    vector <pair <ll, ll>> vec;
    for(ll i=1; i<=n; i++){
        if(niz[i] != i){
            vec.push_back({niz[i], i});
        }
    }
    sort(vec.begin(), vec.end());
    ll prosli = n+1;
    ll g = vec.size();
    ll sol = 1;
    for(auto par : vec){
        ll a = par.first;
        ll b = par.second;
        sol = mul(sol, pw(g, max(0LL, a-prosli)));
        prosli = a+1;
        g--;
    }
    if(vec.size() == n) sol = mul(sol, n);
    return sol;
}

Compilation message (stderr)

gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:103:12: warning: unused variable 'b' [-Wunused-variable]
         ll b = par.second;
            ^
gondola.cpp:108:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(vec.size() == n) sol = mul(sol, n);
        ~~~~~~~~~~~^~~~

• 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