제출 #913248

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
913248		12345678	곤돌라 (IOI14_gondola)	C++17	75 / 100	43 ms	4692 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);
    long long ans=1, l;
    set<pair<int, int>> s;
    for (int i=0; i<n; i++) if (inputSeq[i]>n) s.insert({inputSeq[i], i});
    if (s.size()==n) for (int i=1; i<=n; i++) ans=(ans*i)%mod;
    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;
}

컴파일 시 표준 에러 (stderr) 메시지

gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:59:17: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   59 |     if (s.size()==n) for (int i=1; i<=n; i++) ans=(ans*i)%mod;
      |         ~~~~~~~~^~~
gondola.cpp:55:9: warning: unused variable 'cnt' [-Wunused-variable]
   55 |     int cnt(0), sz(n+1);
      |         ^~~

• 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