Submission #582238

#	Time	Username	Problem	Language	Result	Execution time	Memory
582238		Drew_	Gondola (IOI14_gondola)	C++17	75 / 100	20 ms	3328 KiB

gondola

#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair
#define f1 first
#define s2 second

using ii = pair<int, int>;

const int MAX = 250069;
const int mod = 1e9 + 9;

template<int MOD = mod>
struct Mint
{
    int val;

    Mint() : val(0) {}
    Mint(int64_t _val) : val((int)(_val % MOD)) { if (val < 0) val += MOD; }

    Mint& operator+= (const Mint &rhs) { val += rhs.val; if (val >= MOD) val -= MOD; return *this; }
    Mint& operator-= (const Mint &rhs) { val -= rhs.val; if (val < 0) val += MOD; return *this; }
    Mint& operator*= (const Mint &rhs) { val = (int)(1ll * val * rhs.val % MOD); return *this; }

    friend Mint fpow(Mint x, int64_t y)
    {
        Mint res = 1;
        for (; y > 0; y >>= 1, x *= x)
        {
            if (y & 1)
                res *= x;
        }
        return res;
    }
    friend Mint inverse(Mint x) { return fpow(x, MOD-2); }
    Mint& operator/= (const Mint &rhs) { return *this *= inverse(rhs); }

    friend Mint operator+ (Mint a, const Mint &b) { return a += b; }
    friend Mint operator- (Mint a, const Mint &b) { return a -= b; }
    friend Mint operator- (Mint a) { return 0 - a; }
    friend Mint operator* (Mint a, const Mint &b) { return a *= b; }
    friend Mint operator/ (Mint a, const Mint &b) { return a /= b; }
    friend ostream& operator<< (ostream &os, const Mint &a) { return os << a.val; }
    friend bool operator== (const Mint &a, const Mint &b) { return a.val == b.val; }
    friend bool operator!= (const Mint &a, const Mint &b) { return a.val != b.val; }
};

int valid(int n, int inputSeq[])
{
    bitset<MAX> vst;
    for (int i = 0; i < n; ++i)
    {
        if (vst[inputSeq[i]])
            return 0;
        vst[inputSeq[i]] = true;
    }

    int pos = -1;
    for (int i = 0; i < n; ++i) if (inputSeq[i] <= n)
    {
        int tmp = (inputSeq[i] - i + n) % n;
        if (pos == -1) pos = tmp;
        if (pos != tmp) return 0;
    }
    return 1;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
    int ar[MAX];
    {
        int pos = 0;
        for (int i = 1; i < n; ++i)
            if (gondolaSeq[i] < gondolaSeq[pos])
                pos = i;

        if (gondolaSeq[pos] <= n)
            pos = (pos - gondolaSeq[pos] + 1 + n) % n;
        else pos = 0;

        iota(ar+pos, ar+n, 1);
        iota(ar, ar+pos, n-pos+1);
    }

    vector<ii> v;
    for (int i = 0; i < n; ++i)
        v.pb({gondolaSeq[i], i});
    sort(v.begin(), v.end());

    int sz = 0, cur = n+1;
    for (auto &[x, pos] : v)
    {
        while (ar[pos] != x)
        {
            replacementSeq[sz++] = ar[pos];
            ar[pos] = cur++;
        }
    }

    return sz;
}

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

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

    int ar[MAX];
    {
        int pos = 0;
        for (int i = 1; i < n; ++i)
            if (inputSeq[i] < inputSeq[pos])
                pos = i;

        if (inputSeq[pos] <= n)
            pos = (pos - inputSeq[pos] + 1 + n) % n;
        else pos = 0;

        iota(ar+pos, ar+n, 1);
        iota(ar, ar+pos, n-pos+1);
    }

    vector<ii> v;
    for (int i = 0; i < n; ++i)
        v.pb({inputSeq[i], i});
    sort(v.begin(), v.end());

    Mint<> res = 1;
    int cur = n+1, rem = 0;
    for (int i = 0; i < n; ++i)
        rem += inputSeq[i] != ar[i];

    for (auto &[x, pos] : v)
    {
        while (ar[pos] != x)
        {
            if (x == cur) rem--;
            else res *= rem;

            ar[pos] = cur++;
        }
    }


    return res.val;
}

• 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: 0 / 15
• Subtask 10: 0 / 10