제출 #102425

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
102425		ansol4328	곤돌라 (IOI14_gondola)	C++11	100 / 100	42 ms	2484 KiB

gondola

#include "gondola.h"
#include<stack>
#include<utility>
#include<queue>
#include<algorithm>

using namespace std;
typedef pair<int,int> P;
typedef long long ll;

int m2[100005];
bool exist[250005];
int res[250005], origin[100005];
const ll MOD=1e9+9;

int valid(int N, int *M)
{
    int val=M[0], idx=0;
    for(int i=0 ; i<N ; i++) m2[i]=M[i];
    sort(m2,m2+N);
    for(int i=1 ; i<N ; i++)
    {
        if(m2[i]==m2[i-1]) return 0;
    }
    for(int i=1 ; i<N ; i++)
    {
        if(val>M[i]) val=M[i], idx=i;
    }
    if(val>N) return 1;
    int nxt=val;
    for(int i=1 ; i<N ; i++)
    {
        (idx+=1)%=N;
        nxt++;
        if(nxt>N) nxt=1;
        if(M[idx]>N) continue;
        if(M[idx]!=nxt) return 0;
    }
    return 1;
}

void make_origin(int N, int *M)
{
    int val=M[0], idx=0;
    for(int i=1 ; i<N ; i++) if(val>M[i]) val=M[i], idx=i;
    if(val>N)
    {
        for(int i=0 ; i<N ; i++) origin[i]=i+1;
        return;
    }
    int nxt=val;
    origin[idx]=nxt;
    for(int i=1 ; i<N ; i++)
    {
        (idx+=1)%=N;
        nxt++;
        if(nxt>N) nxt=1;
        origin[idx]=nxt;
    }
}

int replacement(int N, int *M, int *ret)
{
    make_origin(N,M);
    priority_queue<P> PQ;
    for(int i=0 ; i<N ; i++)
    {
        exist[M[i]]=true;
        PQ.push(P(M[i],i));
    }
    stack<int> S;
    int idx=PQ.top().first;
    while(PQ.top().first!=N)
    {
        int pval, tsec=PQ.top().second;
        while(exist[idx]) idx--;
        pval=idx;
        if(idx<=N) pval=origin[tsec];
        PQ.pop();
        PQ.push(P(pval,tsec));
        exist[pval]=true;
        S.push(pval);
    }
    int rcnt=0;
    while(!S.empty())
    {
        ret[rcnt++]=S.top();
        S.pop();
    }
    return rcnt;
}

ll get_pow(ll x, int y)
{
    if(y==0) return 1;
    if(y==1) return x;
    ll ret=get_pow(x,y/2);
    (ret*=ret)%=MOD;
    if(y%2==1) (ret*=x)%=MOD;
    return ret;
}

int countReplacement(int N, int *M)
{
    int val=M[0], idx=0;
    ll ret=0, ecnt=0;
    if(!valid(N,M)) return (int)ret;
    for(int i=1 ; i<N ; i++) if(val>M[i]) val=M[i], idx=i;
    priority_queue<int,vector<int>,greater<int> > PQ;
    if(val>N)
    {
        ret=N, ecnt=N;
        for(int i=0 ; i<N ; i++) PQ.push(M[i]);
    }
    else
    {
        ret=1;
        int nxt=val;
        for(int i=1 ; i<N ; i++)
        {
            (idx+=1)%=N;
            nxt++;
            if(nxt>N) nxt=1;
            if(nxt!=M[idx]) PQ.push(M[idx]), ecnt++;
        }
    }
    val=N+1;
    while(!PQ.empty())
    {
        int y=PQ.top()-val;
        (ret*=get_pow(ecnt,y))%=MOD;
        ecnt--;
        val=PQ.top()+1;
        PQ.pop();
    }
    return (int)ret;
}

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