oj.uz

Submission #931827

# Submission time Handle Problem Language Result Execution time Memory
931827 2024-02-22T11:34:17 Z OAleksa Gondola (IOI14_gondola) C++14
75 / 100
 30 ms 6096 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 = [&](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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 0 ms 376 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 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 352 KB Output is correct
6 Correct 9 ms 2776 KB Output is correct
7 Correct 27 ms 4836 KB Output is correct
8 Correct 21 ms 4808 KB Output is correct
9 Correct 7 ms 1752 KB Output is correct
10 Correct 20 ms 5584 KB Output is correct

Subtask #3
10.0 / 10.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 352 KB Output is correct
4 Correct 0 ms 352 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 13 ms 2776 KB Output is correct
7 Correct 23 ms 4868 KB Output is correct
8 Correct 16 ms 4804 KB Output is correct
9 Correct 5 ms 1856 KB Output is correct
10 Correct 19 ms 5584 KB Output is correct
11 Correct 1 ms 352 KB Output is correct
12 Correct 0 ms 436 KB Output is correct
13 Correct 12 ms 2512 KB Output is correct
14 Correct 0 ms 352 KB Output is correct
15 Correct 30 ms 5840 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 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 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 1 ms 504 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 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 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

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 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 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 19 ms 5468 KB Output is correct
12 Correct 22 ms 6096 KB Output is correct
13 Correct 20 ms 3268 KB Output is correct
14 Correct 21 ms 5324 KB Output is correct
15 Correct 20 ms 3224 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 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 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 444 KB Output is correct
6 Correct 1 ms 444 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 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 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 30 ms 5132 KB Output is correct
10 Correct 25 ms 4308 KB Output is correct
11 Correct 10 ms 1752 KB Output is correct
12 Correct 11 ms 2008 KB Output is correct
13 Incorrect 3 ms 860 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #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 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 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 30 ms 5080 KB Output is correct
10 Correct 26 ms 4232 KB Output is correct
11 Correct 9 ms 1756 KB Output is correct
12 Correct 11 ms 2016 KB Output is correct
13 Incorrect 3 ms 880 KB Output isn't correct
14 Halted 0 ms 0 KB -