Submission #374166

#	Time	Username	Problem	Language	Result	Execution time	Memory
374166		ritul_kr_singh	Gondola (IOI14_gondola)	C++17	40 / 100	57 ms	7532 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;

    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;
    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, res = n;
    ll inp0[n];
    for(ll ii=0, i=ind; ii<n; ++ii, i=(i+1)%n) inp0[i] = ii+least;

    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 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));
        if(res >= MOD) res -= MOD;
        --left;
        extra = inp[i] + 1;
    }
    return res;
}

Compilation message (stderr)

gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:75:8: warning: variable 'inp0' set but not used [-Wunused-but-set-variable]
   75 |     ll inp0[n];
      |        ^~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 10 / 10
• Subtask 4: 0 / 5
• Subtask 5: 0 / 10
• Subtask 6: 0 / 20
• Subtask 7: 5 / 5
• Subtask 8: 15 / 15
• Subtask 9: 0 / 15
• Subtask 10: 0 / 10