Submission #931827

#	Time	Username	Problem	Language	Result	Execution time	Memory
931827		OAleksa	Gondola (IOI14_gondola)	C++14	75 / 100	30 ms	6096 KiB

gondola

#include "gondola.h"
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;

int valid(int n, int input[])
{
   vector<int> a;
   for (int i = 0;i < n;i++)
      a.push_back(input[i]);
   for (int i = 0;i < n;i++)
      a.push_back(input[i]);
   int mn = -1;
   map<int, int> cnt;
   for (int i = 0;i < n;i++) {
      cnt[a[i]]++;
      if (mn == -1 || a[i] < a[mn])
         mn = i;
   }
   for (auto u : cnt) {
      if (u.s > 1)
         return 0;
   }
   for (int i = mn, j = 0;j < n;i++,j++) {
      if (a[i] > n)
         continue;
      if (a[i] != a[mn] + j)
         return 0;
   }
   return 1;
}

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

int replacement(int n, int g[], int ans[])
{
   int sz = 0;
   if (!valid(n, g))
      return sz;
   vector<int> a;
   for (int i = 0;i < n;i++)
      a.push_back(g[i]);
   for (int i = 0;i < n;i++)
      a.push_back(g[i]);
   int mn = -1;
   for (int i = 0;i < n;i++) {
      if (a[i] <= n && (mn == -1 || a[i] < a[mn]))
         mn = i;
   }
   vector<pair<int, int>> pos;
   if (mn == -1) {
      mn = 0;
      for (int i = 0;i < n;i++) {
         if (a[i] < a[mn])
            mn = i;
      }
      for (int i = mn, j = 1;j <= n;i++, j++) {
         pos.push_back({a[i], j});
      }
   }
   else {
      for (int i = mn, j = 0;j < n;i++, j++) {
         if (a[i] > n) {
            int x = a[mn] + j;
            if (x > n)
               x -= n;
            pos.push_back({a[i], x});
         }
      }
   }
   sort(pos.begin(), pos.end());
   int lst = n;
   for (auto i : pos) {
      int br = i.s, x = i.f;
      while (x > lst) {
         ans[sz++] = br;
         br = ++lst;
      }
   }
   return sz;
}

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

int countReplacement(int n, int g[])
{
   const int mod = 1e9 + 9;
   auto mul = [&](long long a, long long b) {
      long long r = a * b;
      if (r >= mod)
         r %= mod;
      return r;
   };
   auto binpow = [&](long long a, long long b) {
      long long res = 1;
      while (b > 0) {
         if (b & 1)
            res = mul(res, a);
         a = mul(a, a);
         b >>= 1;
      }
      return res;
   };
   if (!valid(n, g))
      return 0;
   vector<int> p;
   for (int i = 0;i < n;i++) {
      if (g[i] >  n)
         p.push_back(g[i]);
   }
   sort(p.begin(), p.end());
   int m = p.size();
   int lst = n;
   int ans = 1;
   for (int i = 0;i < m;i++) {
      int r = p[i] - lst;
      long long x = 1;
      for (int j = 0;j < r - 1;j++)
         x = mul(x, m - i);
      ans = mul(ans, x);
      lst = p[i];
   }
   return ans;
}

Compilation message (stderr)

gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:95:9: warning: variable 'binpow' set but not used [-Wunused-but-set-variable]
   95 |    auto binpow = [&](long long a, long long b) {
      |         ^~~~~~

• 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