Submission #1065664

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065664		andrei_iorgulescu	Gondola (IOI14_gondola)	C++14	55 / 100	25 ms	10840 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 countReplacement(int n, int inputSeq[])
{
    return -1;
}

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)
      |         ~~~~~~~~~~~^~~~

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