Submission #295501

#	Time	Username	Problem	Language	Result	Execution time	Memory
295501		stoyan_malinin	Gondola (IOI14_gondola)	C++14	90 / 100	94 ms	7920 KiB

gondola

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

#include <map>
#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;
        int lastRelevant = -1;
        for(int i = 1;i<n;i++)
        {
            if(a[i]>relevant) sortedL[i] = sortedL[i-1];
            else sortedL[i] = (sortedL[i-1]&(lastRelevant<a[i])), lastRelevant = a[i];
        }

        lastRelevant = MAXN;
        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]<lastRelevant)), lastRelevant = a[i];
        }

        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]==n) &&
                       ((a[i+1]>relevant && seen[1]==false) || a[i+1]==1))
                    {
                        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;
    }

    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++;
            }
        }

        return answer;
    }
};

namespace CountReplacements
{
    const long long mod = 1e9 + 9;

    struct FenwickTree
    {
        int n;
        int tree[MAXN];

        FenwickTree(){}
        FenwickTree(int n)
        {
            this->n = n;
            memset(this->tree, 0, sizeof(this->tree));
        }

        void update(int ind, int val)
        {
            ind++;
            while(ind<=n)
            {
                tree[ind] += val;
                ind += ind&(-ind);
            }
        }

        int query(int ind)
        {
            ind++;
            int sum = 0;

            while(ind>0)
            {
                sum += tree[ind];
                ind -= ind&(-ind);
            }

            return sum;
        }
    };



    long long fastPow(long long x, long long p)
    {
        long long ans = 1, curr = x;

        while(p!=0)
        {
            if(p%2!=0) ans = (ans*curr)%mod;

            p/=2;
            curr = (curr*curr)%mod;
        }

        return ans;
    }

    long long inv(long long x)
    {
        return fastPow(x, mod-2);
    }

    map <int, int> code;

    void compress(vector <pair <int, int>> &raw)
    {
        set <int> s;
        for(pair <int, int> x: raw) s.insert(x.second);

        int ind = 0;
        for(int x: s) code[x] = ind, ind++;
    }

    long long solve(vector <pair <int, int>> &raw, int n)
    {
        FenwickTree T(MAXN-5);
        compress(raw);

        int num = n + 1;
        long long answer = 1;

        for(pair <int, int> x: raw)
            T.update(code[x.second], +1);

        for(pair <int, int> x: raw)
        {
            while(num<x.first)
            {
                int cnt = T.query(num-1);

                answer = (answer*cnt)%mod;
                num++;
            }
            if(num==x.first)
            {
                T.update(code[x.second], -1);

                num++;
                continue;
            }
        }

        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[])
{
    if(Valid::check(n, inputSeq, n)==false) return 0;

    vector <pair <int, int>> raw;
    if(Replacement::checkSpecial(n, inputSeq)==false) raw = Replacement::genRaw(n, inputSeq);
    else raw = Replacement::genRawSpecial(n, inputSeq);
    sort(raw.begin(), raw.end());

    long long answer = CountReplacements::solve(raw, n);
    if(Replacement::checkSpecial(n, inputSeq)==true) answer = (answer*n)%CountReplacements::mod;

    return answer;
}

Compilation message (stderr)

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:296:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  296 |     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: 5 / 5
• Subtask 8: 15 / 15
• Subtask 9: 15 / 15
• Subtask 10: 0 / 10