Submission #295515

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
295515	2020-09-09T17:53:27 Z	stoyan_malinin	Gondola (IOI14_gondola)	C++14	100 / 100	216 ms	15380 KB

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 = 1e6 + 5;

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

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

        set <int> s;
        for(int i = 0;i<n;i++)
        {
            if(s.count(a[i])==true) return false;
            s.insert(a[i]);
        }


        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 && s.count(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 && s.count(n)==false) || a[i]==n) &&
                       ((a[i+1]>relevant && s.count(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);

        long long 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)
            {
                auto it = code.lower_bound(num);
                it--;

                int cnt = T.query(it->second);

                answer = (answer*fastPow(cnt, x.first-num))%mod;
                num = x.first;
            }
            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

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

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Correct	0 ms	384 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Correct	1 ms	384 KB	Output is correct

Subtask #2

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	0 ms	384 KB	Output is correct
4	Correct	0 ms	384 KB	Output is correct
5	Correct	0 ms	384 KB	Output is correct
6	Correct	19 ms	2304 KB	Output is correct
7	Correct	14 ms	896 KB	Output is correct
8	Correct	32 ms	4096 KB	Output is correct
9	Correct	9 ms	1536 KB	Output is correct
10	Correct	37 ms	4728 KB	Output is correct

Subtask #3

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Correct	0 ms	384 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Correct	0 ms	384 KB	Output is correct
6	Correct	16 ms	2304 KB	Output is correct
7	Correct	14 ms	1024 KB	Output is correct
8	Correct	32 ms	4096 KB	Output is correct
9	Correct	9 ms	1536 KB	Output is correct
10	Correct	38 ms	4732 KB	Output is correct
11	Correct	0 ms	384 KB	Output is correct
12	Correct	0 ms	384 KB	Output is correct
13	Correct	23 ms	2168 KB	Output is correct
14	Correct	1 ms	384 KB	Output is correct
15	Correct	55 ms	4836 KB	Output is correct

Subtask #4

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	0 ms	256 KB	Output is correct
5	Correct	0 ms	384 KB	Output is correct

Subtask #5

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Correct	0 ms	384 KB	Output is correct
4	Correct	0 ms	384 KB	Output is correct
5	Correct	0 ms	384 KB	Output is correct
6	Correct	0 ms	384 KB	Output is correct
7	Correct	1 ms	384 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	1 ms	384 KB	Output is correct
10	Correct	1 ms	384 KB	Output is correct

Subtask #6

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Correct	0 ms	384 KB	Output is correct
4	Correct	0 ms	384 KB	Output is correct
5	Correct	0 ms	384 KB	Output is correct
6	Correct	1 ms	384 KB	Output is correct
7	Correct	1 ms	384 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	1 ms	384 KB	Output is correct
10	Correct	1 ms	384 KB	Output is correct
11	Correct	11 ms	640 KB	Output is correct
12	Correct	13 ms	720 KB	Output is correct
13	Correct	18 ms	1404 KB	Output is correct
14	Correct	11 ms	640 KB	Output is correct
15	Correct	26 ms	2264 KB	Output is correct

Subtask #7

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4224 KB	Output is correct
2	Correct	3 ms	4224 KB	Output is correct
3	Correct	3 ms	4224 KB	Output is correct

Subtask #8

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4224 KB	Output is correct
2	Correct	3 ms	4224 KB	Output is correct
3	Correct	3 ms	4224 KB	Output is correct
4	Correct	3 ms	4224 KB	Output is correct
5	Correct	3 ms	4224 KB	Output is correct
6	Correct	3 ms	4224 KB	Output is correct
7	Correct	3 ms	4224 KB	Output is correct
8	Correct	3 ms	4224 KB	Output is correct

Subtask #9

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4224 KB	Output is correct
2	Correct	3 ms	4224 KB	Output is correct
3	Correct	3 ms	4224 KB	Output is correct
4	Correct	3 ms	4224 KB	Output is correct
5	Correct	3 ms	4224 KB	Output is correct
6	Correct	3 ms	4224 KB	Output is correct
7	Correct	3 ms	4224 KB	Output is correct
8	Correct	3 ms	4224 KB	Output is correct
9	Correct	132 ms	10612 KB	Output is correct
10	Correct	91 ms	8900 KB	Output is correct
11	Correct	38 ms	6632 KB	Output is correct
12	Correct	48 ms	7156 KB	Output is correct
13	Correct	11 ms	4936 KB	Output is correct

Subtask #10

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4224 KB	Output is correct
2	Correct	3 ms	4224 KB	Output is correct
3	Correct	3 ms	4224 KB	Output is correct
4	Correct	4 ms	4224 KB	Output is correct
5	Correct	3 ms	4224 KB	Output is correct
6	Correct	3 ms	4224 KB	Output is correct
7	Correct	3 ms	4224 KB	Output is correct
8	Correct	3 ms	4224 KB	Output is correct
9	Correct	124 ms	10564 KB	Output is correct
10	Correct	97 ms	9028 KB	Output is correct
11	Correct	40 ms	6624 KB	Output is correct
12	Correct	48 ms	7164 KB	Output is correct
13	Correct	12 ms	5064 KB	Output is correct
14	Correct	185 ms	13200 KB	Output is correct
15	Correct	216 ms	15380 KB	Output is correct
16	Correct	31 ms	6340 KB	Output is correct
17	Correct	132 ms	11860 KB	Output is correct
18	Correct	71 ms	8420 KB	Output is correct