제출 #410949

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
410949		MDario	곤돌라 (IOI14_gondola)	C++11	75 / 100	48 ms	4500 KiB

gondola

#include "gondola.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
const ll mod=1e9+9;
ll qpow(ll xf, ll yf){
    if(yf==0)return 1;
    if(yf&1)return (qpow(xf, yf-1)*xf)%mod;
    return qpow((xf*xf)%mod, yf/2);
}
int valid(int n, int a[]){
    map<int, int>m;
    int c=0;
    for(int i=0; i<n; i++){
        if(m[a[i]]){
            return 0;
        }
        m[a[i]]=1;
        if(a[i]<=n){
            if(c==0){
                c=(a[i]-i+n-1)%n+1;
            }
            else if((a[i]-i+n-1)%n+1!=c){
                return 0;
            }
        }
    }
    return 1;
}

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

int replacement(int n, int a[], int replacementSeq[]){
    vector<pair<int, int>> v;
    int c=0;
    for(int i=0; i<n; i++){
        if(a[i]<=n)c=(a[i]-i+n-1)%n+1;
    }
    if(c==0){
        for(int i=0; i<n; i++){
            v.push_back({a[i], i+1});
        }
    }
    else{
        for(int i=0; i<n; i++){
            v.push_back({a[i], (c+i-1)%n+1});
        }
    }
    sort(v.begin(), v.end());
    c=n+1;
    for(int i=0; i<n; i++){
        while(v[i].F>v[i].S){
            replacementSeq[c-n-1]=v[i].S;
            v[i].S=c;
            c++;
        }
    }
    return c-n-1;
}

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

int countReplacement(int n, int a[]){
    if(!valid(n, a))return 0;
    vector<ll> v;
    ll c=n+1, c1=0;
    for(int i=0; i<n; i++){
        if(a[i]>n)v.push_back(a[i]);
    }
    sort(v.begin(), v.end());
    c1=v.size();
    ll r=1;
    for(int i=0; i<c1; i++){
        r=(r*qpow(c1-i, v[i]-c))%mod;
        c=v[i]+1;
    }
    return r;
}

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