Submission #341106

#	Time	Username	Problem	Language	Result	Execution time	Memory
341106		mohamedsobhi777	Gondola (IOI14_gondola)	C++14	100 / 100	108 ms	7024 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[])
{
       using ll = long long;
       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;
       ll rem = n;
       for (int i = 0; i < n; ++i)
              if (inputSeq[i] <= n)
                     --rem;
       if (rem == n)
              ans = n;
       auto faspow = [&](ll x, ll y) -> long long {
              ll ret = 1ll;
              while (y)
              {
                     if (y & 1)
                            ret = 1ll * ret * x % mod;
                     x = 1ll * x * x % mod;
                     y >>= 1ll;
              }
              return ret;
       };
       vector<int> nxts;
       for (int i = 0; i < n; ++i)
       {
              if (inputSeq[i] > n)
              {
                     nxts.push_back(inputSeq[i]);
              }
       }
       sort(nxts.begin(), nxts.end());
       int lst = n + 1;
       for (auto u : nxts)
       {
              ans = 1ll * ans * faspow(rem, u - lst) % mod;
              --rem;
              lst = u + 1;
       }
       assert(ans);
       return ans;
}

Compilation message (stderr)

gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:101:12: warning: unused variable 'nxt' [-Wunused-variable]
  101 |        int nxt = n + 1;
      |            ^~~
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: 15 / 15
• Subtask 10: 10 / 10