Submission #420948

#	Time	Username	Problem	Language	Result	Execution time	Memory
420948		Peti	Gondola (IOI14_gondola)	C++14	60 / 100	52 ms	4588 KiB

gondola

#include <bits/stdc++.h>
#include "gondola.h"

using namespace std;

int valid(int n, int t[])
{
    rotate(t, min_element(t, t+n), t+n);
    map<int, int> num;
    int last = -n-1;
    bool jo = true;
    for(int i = 0; i < n; i++){
        last++;
        num[t[i]]++;
        if(t[i] <= n){
            if(last < 0)
                last = t[i];
            else if(t[i] != last)
                jo = false;
        }
    }

    for(auto p : num)
        if(p.second > 1)
            return 0;

    return (int)jo;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
    for(int i = 0; i < n; i++){
        if(gondolaSeq[i] <= n){
            int x = i-gondolaSeq[i]+1;
            if(x < 0) x += n;
            rotate(gondolaSeq, gondolaSeq + x, gondolaSeq + n);
            break;
        }
    }

    vector<pair<int, int>> v;
    for(int i = 0; i < n; i++)
        if(gondolaSeq[i] > n)
            v.emplace_back(gondolaSeq[i], i+1);
    sort(v.begin(), v.end());

    int ret = 0, x = n;
    for(auto p : v){
        while(x < p.first){
            replacementSeq[ret++] = p.second;
            p.second = ++x;
        }
    }

    return ret;
}

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

const long long mod = (long long)1e9+9;
long long hatvany(long long n, long long h){
    return (h ? hatvany(n*n%mod, h>>1)*(h&1ll ? n : 1ll)%mod : 1ll);
}

int countReplacement(int n, int inputSeq[])
{
    if(!valid(n, inputSeq))
        return 0;

    bool fix = false;
    vector<int> v;
    for(int i = 0; i < n; i++){
        if(inputSeq[i] <= n)
            fix = true;
        else
            v.push_back(inputSeq[i]);
    }

    if(v.empty())
        return 1;

    sort(v.begin(), v.end());
    long long meg = 1, last = n, db = (long long)v.size();
    for(long long x : v){
        meg = (meg * hatvany(db, x-last-1ll))%mod;
        last = x;
    }

    return meg * (!fix ? (long long)n : 1ll) % mod;
}

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