제출 #420932

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
420932		Peti	곤돌라 (IOI14_gondola)	C++14	20 / 100	38 ms	5308 KiB

gondola

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

using namespace std;

int valid(int n, int t[])
{
    vector<int> v;
    map<int, int> num;
    for(int i = 0; i < n; i++){
        num[t[i]]++;
        if(t[i] <= n)
            v.push_back(t[i]);
    }

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

    rotate(v.begin(), min_element(v.begin(), v.end()), v.end());
    for(int i = 1; i < (int)v.size(); i++)
        if(v[i-1] > v[i])
            return 0;

    return 1;
}

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

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;
            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: 0 / 10
• Subtask 4: 5 / 5
• Subtask 5: 0 / 10
• Subtask 6: 0 / 20
• Subtask 7: 5 / 5
• Subtask 8: 0 / 15
• Subtask 9: 0 / 15
• Subtask 10: 0 / 10