Submission #295221

#	Time	Username	Problem	Language	Result	Execution time	Memory
295221		stoyan_malinin	Gondola (IOI14_gondola)	C++14	55 / 100	25 ms	2384 KiB

gondola

#include "gondola.h"
//#include "grader.cpp"

#include <set>
#include <vector>
#include <cstring>
#include <assert.h>
#include <iostream>
#include <algorithm>

using namespace std;

const int MAXN = 3e5 + 5;

namespace Valid
{
    bool seen[MAXN];
    bool sortedL[MAXN], sortedR[MAXN];

    void fillSeen(int n, int a[], int maxVal)
    {
        for(int i = 0;i<=maxVal;i++)
        {
            seen[i] = false;
        }
        for(int i = 0;i<n;i++)
        {
            seen[ a[i] ] = true;
        }
    }

    bool check(int n, int a[], int relevant)
    {
        int maxVal = 0;
        for(int i = 0;i<n;i++)
        {
            maxVal = max(maxVal, a[i]);
            sortedL[i] = sortedR[i] = false;
        }

        for(int i = 0;i<=maxVal;i++)
        {
            seen[i] = false;
        }

        for(int i = 0;i<n;i++)
        {
            if(seen[ a[i] ]==true) return false;
            seen[ a[i] ] = true;
        }

        sortedL[0] = true;
        for(int i = 1;i<n;i++)
        {
            if(a[i]>relevant) sortedL[i] = sortedL[i-1];
            else sortedL[i] = (sortedL[i-1]&(a[i-1]<a[i]));
        }

        sortedR[n-1] = true;
        for(int i = n-2;i>=0;i--)
        {
            if(a[i]>relevant) sortedR[i] = sortedR[i+1];
            else sortedR[i] = (sortedR[i+1]&(a[i]<a[i+1]));
        }

        if(sortedL[n-1]==true && (a[n-1]==n || (a[n-1]>relevant && seen[n]==false))) return true;
        for(int i = 0;i<n-1;i++)
        {
            if(sortedL[i]==true && sortedR[i+1]==true)
            {
                if(a[i]>relevant || a[i+1]>relevant)
                {
                    if((a[i]>relevant && seen[n]==false) && (a[i+1]>relevant && seen[1]==false))
                    {
                        return true;
                    }
                }
                else
                {
                    if(a[i]==n && a[i+1]==1)
                    {
                        return true;
                    }
                }
            }
        }

        return false;
    }
};

namespace Replacement
{
    bool checkSpecial(int n, int a[])
    {
        for(int i = 0;i<n;i++)
        {
            if(a[i]<=n) return false;
        }

        return true;
    }

    //1 2 3 4
    //4 1 2 3
    //3 4 1 3
    vector <pair <int, int>> genRaw(int n, int a[])
    {
        int shift = -1;
        for(int i = 0;i<n;i++)
        {
            if(a[i]<=n)
            {
                if(a[i]<=i+1) shift = (i + 1) - a[i];
                else shift = (n - a[i]) + (i + 1);

                break;
            }
        }

        vector <pair <int, int>> out;
        for(int i = 0;i<n;i++)
        {
            if(a[i]>n)
            {
                out.push_back({a[i], (i-shift+n)%n+1});
            }
        }

        return out;
    }

    vector <pair <int, int>> genRawSpecial(int n, int a[])
    {
        vector <pair <int, int>> out;
        for(int i = 0;i<n;i++)
        {
            out.push_back({a[i], i+1});
        }

        return out;
    }

    vector <int> solve(int n, int a[])
    {
        vector <int> answer;

        vector <pair <int, int>> raw;
        if(checkSpecial(n, a)==false) raw = genRaw(n, a);
        else raw = genRawSpecial(n, a);


        int num = n + 1;
        sort(raw.begin(), raw.end());
        for(pair <int, int> x: raw)
        {
            if(num!=x.first)
            {
                answer.push_back(x.second);

                num++;
                while(num<=x.first)
                {
                    answer.push_back(num-1);
                    num++;
                }
            }
            else
            {
                answer.push_back(x.second);
                num++;
            }
        }

        //for(pair <int, int> x: raw) cout << x.first << " " << x.second << " || ";
        //cout << '\n';

        return answer;
    }
};

int valid(int n, int inputSeq[])
{
  return Valid::check(n, inputSeq, n);
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
    vector <int> v = Replacement::solve(n, gondolaSeq);
    for(int i = 0;i<v.size();i++) replacementSeq[i] = v[i];

    return v.size();
}

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

int countReplacement(int n, int inputSeq[])
{
  return -3;
}

//1 2 3 4 5
//6 7 8 9 10

Compilation message (stderr)

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:192:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  192 |     for(int i = 0;i<v.size();i++) replacementSeq[i] = v[i];
      |                   ~^~~~~~~~~

• 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