제출 #341095

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
341095		mohamedsobhi777	곤돌라 (IOI14_gondola)	C++14	75 / 100	90 ms	10476 KiB

gondola

#include <bits/stdc++.h>

const int mod = 1e9 + 9;
using namespace std;
#define f first
#define s second
#include "gondola.h"

int valid(int n, int inputSeq[])
{
       map<int, int> mp;
       for (int i = 0; i < n; ++i)
              if (mp[inputSeq[i]]++)
                     return 0;
       if (*min_element(inputSeq, inputSeq + n) > n)
              return 1;
       for (int i = 0; i < n; ++i)
              inputSeq[i]--;

       auto check = [&](int i) -> bool {
              bool ret1 = 1;
              for (int j = 1; j < n; ++j)
              {
                     int nxt = (i + j) % n;
                     if (inputSeq[nxt] >= n)
                            continue;
                     if (inputSeq[nxt] != (inputSeq[i] + j) % n)
                            ret1 = 0;
              }
              return ret1;
       };
       for (int i = 0; i < n; ++i)
       {
              if (inputSeq[i] < n)
                     return check(i);
       }
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
       for (int i = 0; i < n; ++i)
              gondolaSeq[i]--;
       vector<int> a(n);
       if (*min_element(gondolaSeq, gondolaSeq + n) >= n)
       {
              iota(a.begin(), a.end(), 0);
       }
       else
       {
              for (int i = 0; i < n; ++i)
              {
                     if (gondolaSeq[i] < n)
                     {
                            for (int j = 0; j < n; ++j)
                            {
                                   a[(i + j) % n] = (gondolaSeq[i] + j) % n;
                            }
                            break;
                     }
              }
       }
       vector<pair<int, int>> v;
       for (int i = 0; i < n; ++i)
       {
              v.push_back({gondolaSeq[i], i});
       }
       sort(v.begin(), v.end());
       int l = 0;
       int nxt = n;

       for (int i = 0; i < n; ++i)
       {
              int j = v[i].s;
              while (a[j] < gondolaSeq[j])
              {
                     replacementSeq[l++] = a[j] + 1;
                     a[j] = nxt++;
              }
       }
       return l;
}

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

int countReplacement(int n, int inputSeq[])
{
       int inpo[n];
       for (int i = 0; i < n; ++i)
              inpo[i] = inputSeq[i];
       if (!valid(n, inpo))
              return 0;
       map<int, int> mp;
       for (int i = 0; i < n; ++i)
       {
              mp[inputSeq[i]]++;
       }
       long long ans = 1;
       int nxt = n + 1;
       int rem = n;
       for (int i = 0; i < n; ++i)
              if (inputSeq[i] <= n)
                     --rem;
       while (rem)
       {
              if (mp[nxt])
                     --rem;
              else
                     ans = 1ll * ans * rem % mod;
              ++nxt;
       }
       assert(ans);
       return ans;
}

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

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:11:22: warning: control reaches end of non-void function [-Wreturn-type]
   11 |        map<int, int> mp;
      |                      ^~

• 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