Submission #1065678

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065678		andrei_iorgulescu	Gondola (IOI14_gondola)	C++14	100 / 100	37 ms	11356 KiB

gondola

#include <bits/stdc++.h>
#include "gondola.h"
#warning That's not FB, that's my FB

using namespace std;

int valid(int n, int inputSeq[])
{
    for (int i = 0; i < n; i++)
        inputSeq[i]--;
    int shift = -1;
    set<int> ele;
    for (int i = 0; i < n; i++)
        ele.insert(inputSeq[i]);
    if (ele.size() != n)
        return 0;
    for (int i = 0; i < n; i++)
    {
        if (inputSeq[i] < n)
        {
            int cur_shift = (n + inputSeq[i] - i) % n;
            if (shift == -1)
                shift = cur_shift;
            else if (shift != cur_shift)
                return 0;
        }
    }
    return 1;
}

int replacement(int n, int gondolaSequence[], int replacementSeq[])
{
    for (int i = 0; i < n; i++)
        gondolaSequence[i]--;
    int mxe = 0;
    for (int i = 0; i < n; i++)
        mxe = max(mxe, gondolaSequence[i]);
    vector<int> pos(mxe + 5), ans(mxe + 5);
    for (int i = 0; i <= mxe; i++)
        pos[i] = -1;
    for (int i = 0; i < n; i++)
        pos[gondolaSequence[i]] = i;
    set<int> spatii;
    for (int i = mxe; i >= 0; i--)
    {
        if (pos[i] == -1)
            ans[i] = *spatii.begin();
        else
            ans[i] = pos[i], spatii.insert(pos[i]);
    }
    int shift = 0;
    for (int i = 0; i < n; i++)
    {
        if (gondolaSequence[i] < n)
        {
            shift = (n + gondolaSequence[i] - i) % n;
        }
    }
    vector<vector<int>> lol(n);
    for (int i = 0; i < n; i++)
        lol[i].push_back((i + shift) % n);
    for (int i = n; i <= mxe; i++)
        lol[ans[i]].push_back(i);
    vector<int> cur(n);
    for (int i = n; i <= mxe; i++)
    {
        replacementSeq[i - n] = lol[ans[i]][cur[ans[i]]];
        cur[ans[i]]++;
    }
    for (int i = 0; i <= mxe - n; i++)
        replacementSeq[i]++;
    return mxe - n + 1;
}

int modulo = (int)1e9 + 9;

int lgpow(int x, int y)
{
    int z = 1;
    while (y != 0)
    {
        if (y % 2 == 1)
            z = 1ll * z * x % modulo;
        x = 1ll * x * x % modulo;
        y /= 2;
    }
    return z;
}

int countReplacement(int n, int inputSeq[])
{
    if (!valid(n, inputSeq))
        return 0;
    //for (int i = 0; i < n; i++)
      //  inputSeq[i]--;
    bool multi_n = true;
    for (int i = 0; i < n; i++)
        if (inputSeq[i] < n)
            multi_n = false;
    vector<int> fx;
    for (int i = 0; i < n; i++)
        if (inputSeq[i] >= n)
            fx.push_back(inputSeq[i]);
    sort(fx.begin(), fx.end());
    reverse(fx.begin(), fx.end());
    int ans = 1;
    for (int i = 0; i < fx.size(); i++)
    {
        if (i + 1 < fx.size())
        {
            int gap = fx[i] - fx[i + 1] - 1;
            ans = 1ll * ans * lgpow(i + 1, gap) % modulo;
        }
        else
        {
            int gap = fx[i] - n;
            ans = 1ll * ans * lgpow(i + 1, gap) % modulo;
        }
    }
    if (multi_n)
        ans = 1ll * ans * n % modulo;
    return ans;
}

Compilation message (stderr)

gondola.cpp:3:2: warning: #warning That's not FB, that's my FB [-Wcpp]
    3 | #warning That's not FB, that's my FB
      |  ^~~~~~~
gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:15:20: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   15 |     if (ele.size() != n)
      |         ~~~~~~~~~~~^~~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:107:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |     for (int i = 0; i < fx.size(); i++)
      |                     ~~^~~~~~~~~~~
gondola.cpp:109:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |         if (i + 1 < fx.size())
      |             ~~~~~~^~~~~~~~~~~

• 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