oj.uz

답안 #295515

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
295515 2020-09-09T17:53:27 Z stoyan_malinin 곤돌라 (IOI14_gondola) C++14
100 / 100
 216 ms 15380 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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