Submission #471433

#	Time	Username	Problem	Language	Result	Execution time	Memory
471433		dung11112003	Gondola (IOI14_gondola)	C++11	60 / 100	22 ms	2120 KiB

gondola

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

#define taskname ""
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define for0(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

using namespace std;

typedef long long ll;
typedef long double ld;
typedef complex <ld> cd;
typedef vector <cd> vcd;
typedef vector <int> vi;

template<class T> using v2d = vector <vector <T> >;
template<class T> bool uin(T &a, T b)
{
    return a > b ? (a = b, true) : false;
}
template<class T> bool uax(T &a, T b)
{
    return a < b ? (a = b, true) : false;
}

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

const ll mod = 1e9 + 9;

int valid(int n, int inputSeq[])
{
    vi vec(inputSeq, inputSeq + n);
    sort(all(vec));
    for0(i, n - 1)
    {
        if (vec[i] == vec[i + 1])
        {
            return 0;
        }
    }
    int d = -1;
    for0(i, n)
    {
        if (inputSeq[i] >= 1 && inputSeq[i] <= n)
        {
            int cur = ((inputSeq[i] - i) % n + n) % n;
            if (d != -1 && d != cur)
            {
                return 0;
            }
            d = cur;
        }
    }
    return 1;
}

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
    for0(i, n)
    {
        if (gondolaSeq[i] >= 1 && gondolaSeq[i] <= n)
        {
            int cur = i;
            int need = gondolaSeq[i] - 1;
            if (need < cur)
            {
                rotate(gondolaSeq, gondolaSeq + cur - need, gondolaSeq + n);
            }
            else if (need > cur)
            {
                rotate(gondolaSeq, gondolaSeq + n - (need - cur), gondolaSeq + n);
            }
            break;
        }
    }
    vi pos((int)2e5 + 1, -1);
    for0(i, n)
    {
        pos[gondolaSeq[i]] = i;
    }
    int mx = *max_element(gondolaSeq, gondolaSeq + n);
    vi a(n);
    iota(all(a), 1);
    int id = 0;
    int ansPos = 0;
    auto addAns = [&](int x)
    {
        replacementSeq[ansPos++] = x;
    };
    fore(i, n + 1, mx)
    {
        if (pos[i] != -1)
        {
            addAns(a[pos[i]]);
            a[pos[i]] = i;
        }
        else
        {
            while (id < n && a[id] == gondolaSeq[id])
            {
                id++;
            }
            addAns(a[id]);
            a[id] = i;
        }
    }
    return ansPos;
}

long long power(long long a, long long b)
{
    long long r = 1;
    while (b)
    {
        if (b & 1)
        {
            r = r * a % mod;
        }
        b /= 2;
        a = a * a % mod;
    }
    return r;
}

int countReplacement(int n, int inputSeq[])
{
    vi vec(inputSeq, inputSeq + n);
    sort(all(vec));
    for0(i, n - 1)
    {
        if (vec[i] == vec[i + 1])
        {
            return 0;
        }
    }
    int d = -1;
    for0(i, n)
    {
        if (inputSeq[i] >= 1 && inputSeq[i] <= n)
        {
            int cur = ((inputSeq[i] - i) % n + n) % n;
            if (d != -1 && d != cur)
            {
                return 0;
            }
            d = cur;
        }
    }
    for0(i, n)
    {
        if (inputSeq[i] >= 1 && inputSeq[i] <= n)
        {
            int cur = i;
            int need = inputSeq[i] - 1;
            if (need < cur)
            {
                rotate(inputSeq, inputSeq + cur - need, inputSeq + n);
            }
            else if (need > cur)
            {
                rotate(inputSeq, inputSeq + n - (need - cur), inputSeq + n);
            }
            break;
        }
    }
    vi a;
    for0(i, n)
    {
        if (inputSeq[i] > n)
        {
            a.pb(inputSeq[i]);
        }
    }
    sort(all(a));
    int cnt = 0;
    for0(i, n)
    {
        cnt += (i + 1 != inputSeq[i]);
    }
    int ans = 1, last = n;
    for (auto &x: a)
    {
        ans = (ll)ans * power(cnt, x - last - 1) % mod;
        cnt--;
    }
    if (d == -1)
    {
        ans = (ll)ans * n % mod;
    }
    return ans;
}

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