Submission #374170

#	Time	Username	Problem	Language	Result	Execution time	Memory
374170		ritul_kr_singh	Gondola (IOI14_gondola)	C++17	100 / 100	79 ms	9068 KiB

gondola

//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#include "gondola.h"
using namespace std;
#define sp << " " <<
#define nl << "\n"
#define ll long long
 
int valid(int n, int a[]){
    ll least = n+1, ind = -1;
    map<ll, ll> m;
    for(ll i=0; i<n; ++i){
        if(a[i] < least) least = a[i], ind = i;
        if(m[a[i]]) return 0;
        ++m[a[i]];
    }
    if(least<=n){
        for(ll ii=0, i=ind; ii<n; ++ii, i=(i+1)%n){
            if(a[i]<=n and a[i]!=ii+least) return 0;
        }
    }
    return 1;
}

int replacement(int n, int* inp, int* ans){
    ll least = n+1, ind = 0;
    for(ll i=0; i<n; ++i){
        if(inp[i] < least) least = inp[i], ind = i;
    }
    if(least>n) least = 1;
    ll inp0[n];
    for(ll ii=0, i=ind; ii<n; ++ii, i=(i+1)%n) inp0[i] = ii+least;
    for(int i=0; i<n; ++i){
        if(inp0[i]>n) inp0[i] -= n;
    }

    vector<pair<ll, ll>> b;
    for(ll i=0; i<n; ++i) b.emplace_back(inp[i], i);
    sort(b.begin(), b.end());

    vector<vector<ll>> a(n);
    ll toPut = 0, extra = n+1;
    for(auto ii : b){
        ll i = ii.second;
        if(inp[i]>n){
            ans[toPut++] = inp0[i];
            for(ll j=extra; j<inp[i]; ++j){
                ans[toPut++] = j;
            }
            extra = inp[i] + 1;
        }
    }
    return toPut;
}

ll modExpo(ll x, ll p){
    ll m = 1e9 + 9;
    ll res = 1, toMul = x % m;
    while(p){
        if(p&1){
            res = (res * toMul) % m;
        }
        toMul = (toMul * toMul) % m;
        p /= 2;
    }
    return res;
}

int countReplacement(int n, int inp[]){
    const ll MOD = 1e9 + 9;
    if(!valid(n, inp)) return 0;
    ll res = 1;
    if(*min_element(inp, inp+n)>n) res = n;

    vector<pair<ll, ll>> b;
    for(ll i=0; i<n; ++i) b.emplace_back(inp[i], i);
    sort(b.begin(), b.end());

    ll extra = n+1, left = 0;
    for(ll i=0; i<n; ++i) left += (inp[i]>n);

    for(auto ii : b){
        ll i = ii.second;
        if(inp[i]<=n) continue;
        ll possible = inp[i] - extra;
        res = (res*modExpo(left, possible));
        res %= MOD;
        --left;
        extra = inp[i] + 1;
    }
    res += MOD;
    res %= MOD;
    return res;
}

• 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