Submission #285700

#	Time	Username	Problem	Language	Result	Execution time	Memory
285700		Kastanda	Gondola (IOI14_gondola)	C++11	100 / 100	76 ms	5496 KiB

gondola

// M
#include<bits/stdc++.h>
#include "gondola.h"
using namespace std;
const int N = 300005, Mod = 1e9 + 9;
int n, A[N];

int valid(int _n, int inputSeq[])
{
        n = _n;
        for (int i = 0; i < n; i ++)
                A[i] = inputSeq[i] - 1;

        int st = -1;
        map < int , int > MP;
        for (int i = 0; i < n; i ++)
        {
                if (MP[A[i]])
                        return 0;
                MP[A[i]] = 1;
                if (A[i] < n)
                        st = i;
        }
        if (st == -1)
                return 1;
        for (int i = 0; i < n; i ++)
                if (A[i] < n)
                {
                        if (i <= st && (A[i] + st - i) % n != A[st])
                                return 0;
                        if (i > st && (A[st] + i - st) % n != A[i])
                                return 0;
                }
        return 1;
}

int replacement(int _n, int gondolaSeq[], int replacementSeq[])
{
        n = _n;
        for (int i = 0; i < n; i ++)
                A[i] = gondolaSeq[i] - 1;

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

        /*int mx = * max_element(A, A + n);
        vector < int > M(mx + 10, 0);
        set < pair < int , int > > ST;
        for (int i = 0; i < n; i ++)
                M[A[i]] = 1, ST.insert({A[i], i});
        int unused = mx;
        while (ST.size())
        {
                int i = ST.rbegin()->second;
                int val = ST.rbegin()->first;
                ST.erase(* ST.rbegin());
                assert(A[i] == val);

                while (unused >= val || M[unused])
                        unused --;
                if (unused >= n)
                {
                        A[i] = unused;
                        M[unused] = 1;
                        ST.insert({A[i], i});
                        continue;
                }
                if (st == -1
        }*/

        vector < int > M(N, -1);
        for (int i = 0; i < n; i ++)
                M[A[i]] = i;

        if (st == -1)
                st = 0;

        int ptr = N - 1, fre = N - 1;
        vector < int > V;
        while (ptr >= n)
        {
                while (M[ptr] == -1 && ptr >= n)
                        ptr --;
                if (ptr < n)
                        break;
                fre = min(fre, ptr - 1);
                int nw = M[ptr]; ptr --;
                while (M[fre] != -1 && fre >= n)
                        fre --;
                if (fre < n)
                {
                        V.push_back((nw - st + n) % n);
                        continue;
                }
                M[fre] = nw;
                V.push_back(fre);
        }
        reverse(V.begin(), V.end());
        for (int i = 0; i < (int)V.size(); i ++)
                replacementSeq[i] = V[i] + 1;
        return ((int)V.size());
}

int Power(int a, int b)
{
        int ret = 1;
        for (; b; b >>= 1, a = 1LL * a * a % Mod)
                if (b & 1) ret = 1LL * ret * a % Mod;
        return ret;
}

int countReplacement(int _n, int inputSeq[])
{
        n = _n;
        for (int i = 0; i < n; i ++)
                A[i] = inputSeq[i];

        if (!valid(n, A))
                return 0;

        vector < int > V;
        for (int i = 0; i < n; i ++)
                V.push_back(A[i]);
        sort(V.begin(), V.end());
        reverse(V.begin(), V.end());
        bool ff = 0;
        while ((int)V.size() && (int)V.back() < n)
                V.pop_back(), ff = 1;
        V.push_back(n - 1);
        int tot = 1;
        for (int i = 1; i < (int)V.size(); i ++)
                tot = 1LL * tot * Power(i, V[i - 1] - V[i] - 1) % Mod;
        if (!ff)
                tot = 1LL * tot * n % Mod;
        return tot;
}

• 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