oj.uz

Submission #931831

# Submission time Handle Problem Language Result Execution time Memory
931831 2024-02-22T11:47:31 Z OAleksa Gondola (IOI14_gondola) C++14
100 / 100
 41 ms 6860 KB 
#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 = [&](int a, int b) {
      long long r = 1ll * a * b;
      if (r >= mod)
         r %= mod;
      return r;
   };
   auto binpow = [&](int a, int b) {
      int 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;
      ans = mul(ans, binpow(m - i, r - 1));
      lst = p[i];
   }
   if (p.size() == n)
      ans = mul(ans, n);
   return ans;
}

Compilation message

gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:121:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  121 |    if (p.size() == n)
      |        ~~~~~~~~~^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 7 ms 2516 KB Output is correct
7 Correct 21 ms 4488 KB Output is correct
8 Correct 17 ms 4556 KB Output is correct
9 Correct 5 ms 1752 KB Output is correct
10 Correct 19 ms 5328 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 8 ms 2516 KB Output is correct
7 Correct 21 ms 4304 KB Output is correct
8 Correct 15 ms 4560 KB Output is correct
9 Correct 5 ms 1752 KB Output is correct
10 Correct 17 ms 5328 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 11 ms 2516 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 28 ms 5516 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 27 ms 4956 KB Output is correct
12 Correct 21 ms 5580 KB Output is correct
13 Correct 19 ms 3008 KB Output is correct
14 Correct 22 ms 4876 KB Output is correct
15 Correct 20 ms 3008 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct

Subtask #8
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 28 ms 4704 KB Output is correct
10 Correct 22 ms 3796 KB Output is correct
11 Correct 8 ms 1752 KB Output is correct
12 Correct 11 ms 2048 KB Output is correct
13 Correct 2 ms 812 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 28 ms 4492 KB Output is correct
10 Correct 23 ms 3820 KB Output is correct
11 Correct 8 ms 1752 KB Output is correct
12 Correct 10 ms 1932 KB Output is correct
13 Correct 2 ms 604 KB Output is correct
14 Correct 36 ms 5948 KB Output is correct
15 Correct 41 ms 6860 KB Output is correct
16 Correct 7 ms 1492 KB Output is correct
17 Correct 27 ms 4768 KB Output is correct
18 Correct 14 ms 2772 KB Output is correct