Submission #98758

#	Time	Username	Problem	Language	Result	Execution time	Memory
98758		Alexa2001	Gondola (IOI14_gondola)	C++17	100 / 100	102 ms	6136 KiB

gondola

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

using namespace std;

const int Nmax = 250005, Mod = 1e9 + 9;
typedef long long ll;

int a[Nmax];

int valid(int n, int A[])
{
    map<int,int> ap;

    int i, rot = Mod;
    for(i=0; i<n; ++i)
        if(A[i] <= n)
        {
            if(rot == Mod) rot = (n + i - A[i]) % n;
                else if(rot != (n + i - A[i]) % n) return 0;
        }
        else ++ap[A[i]];

    for(auto it : ap)
        if(it.second > 1) return 0;
    return 1;
}

bool cmp(int x, int y)
{
    return a[x] < a[y];
}

int replacement(int n, int A[], int ans[])
{
    int i, last = n+1, rot = 0;
    vector<int> v;

    for(i=0; i<n; ++i)
        if(A[i] <= n) rot = (A[i] - 1) - i;
    if(rot < 0) rot += n;

    for(i=0; i<n; ++i) a[(i + rot) % n] = A[i];

    for(i=0; i<n; ++i)
        if(a[i] > n) v.push_back(i);

    sort(v.begin(), v.end(), cmp);

    int nr = 0;
    for(auto it : v)
    {
        ans[nr++] = it+1;
        for(i=last; i<a[it]; ++i) ans[nr++] = i;
        last = a[it] + 1;
    }
    return nr;
}

ll power(ll a, int b)
{
    ll ans = 1;
    while(b)
    {
        if(b&1) ans = ans * a % Mod;
        a = a * a % Mod; b >>= 1;
    }
    return ans;
}

int countReplacement(int n, int A[])
{
    if(!valid(n, A)) return 0;

    int i;
    vector<int> v;
    for(i=0; i<n; ++i)
        if(A[i] > n) v.push_back(A[i] - n);

    sort(v.begin(), v.end());
    int m = v.size();
    ll ans = 1;

    int last = 0;
    for(auto it : v)
    {
        ans *= power(m, it - last - 1);
        ans %= Mod;
        --m;
        last = it;
    }
    if(v.size() == n) ans = ans * n % Mod;
    return (int) ans;
}

Compilation message (stderr)

gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:92:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(v.size() == n) ans = ans * n % 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