제출 #913242

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
913242		12345678	곤돌라 (IOI14_gondola)	C++17	75 / 100	52 ms	4768 KiB

gondola

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

using namespace std;

const int mod=1e9+9;

int valid(int n, int inputSeq[])
{
    set<int> st;
    for (int i=0; i<n; i++) 
    {
        if (st.find(inputSeq[i])!=st.end()) return 0;
        st.insert(inputSeq[i]);
    }
    int s, cnt(0);
    bool can=1;
    pair<int, int> mn={INT_MAX, -1};
    for (int i=0; i<n; i++) mn=min(mn, {inputSeq[i], i});
    if (mn.first>n) return 1;
    cnt=mn.first;
    s=mn.second;
    for (int i=s; i<n; i++) if (inputSeq[i]!=cnt++&&inputSeq[i]<=n) can=0;
    for (int i=0; i<s; i++) if (inputSeq[i]!=cnt++&&inputSeq[i]<=n) can=0;
    return can;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
    int cnt(0), res(0);
    set<pair<int, int>> s;
    for (int i=0; i<n; i++) if (gondolaSeq[i]>n) s.insert({gondolaSeq[i], i});
    pair<int, int> mn={INT_MAX, -1};
    for (int i=0; i<n; i++) if (gondolaSeq[i]<=n) mn=min(mn, {gondolaSeq[i], i});
    if (mn.first==INT_MAX) mn={1, 0};
    cnt=mn.first-1;
    vector<int> p(n);
    for (int i=mn.second; i<n; i++) p[i]=(++cnt)>n?cnt-n:cnt;
    for (int i=0; i<mn.second; i++) p[i]=(++cnt)>n?cnt-n:cnt;
    for (auto [x, y]:s)
    {
        replacementSeq[res++]=p[y];
        while (res+n!=x) replacementSeq[res]=res+n, res++;
    }
    return res;
}

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

int countReplacement(int n, int inputSeq[])
{
    if (!valid(n, inputSeq)) return 0;
    int cnt(0), sz(n+1), l(0);
    long long ans=1;
    set<pair<int, int>> s;
    for (int i=0; i<n; i++) if (inputSeq[i]>n) s.insert({inputSeq[i], i});
    pair<int, int> mn={INT_MAX, -1};
    for (int i=0; i<n; i++) if (inputSeq[i]<=n) mn=min(mn, {inputSeq[i], i});
    if (mn.first==INT_MAX) mn={1, 0};
    cnt=mn.first-1;
    vector<int> p(n);
    for (int i=mn.second; i<n; i++) p[i]=(++cnt)>n?cnt-n:cnt;
    for (int i=0; i<mn.second; i++) p[i]=(++cnt)>n?cnt-n:cnt;
    l=s.size();
    for (auto [x, y]:s)
    {
        while (sz!=x) ans=(ans*l)%mod, sz++;
        sz++;
        l--;
        //cout<<x<<' '<<y<<' '<<ans<<' '<<l<<'\n';
    }
    return ans;
}

• 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