oj.uz

Submission #799461

# Submission time Handle Problem Language Result Execution time Memory
799461 2023-07-31T14:48:37 Z erray Gondola (IOI14_gondola) C++17
100 / 100
 37 ms 6700 KB 
#include "gondola.h"
#include <bits/stdc++.h>
 
using namespace std;
 
#ifdef DEBUG
  #include "/home/ioi/codes/ioi14_d2/debug.h"
#else 
  #define debug(...) void(37)
#endif
 
template<typename T> 
vector<T> inverse_fuck(T* a, int N) {
  vector<T> res(N);
  for (int i = 0; i < N; ++i) {
    res[i] = a[i];
  }
  return res;
}
 
constexpr int md = 1000000009;
struct Mint {
  int val = 0;
  Mint() : val(0) { } 
  template<typename T>
  Mint(T x) {
    if (-md <= x && x < md) {
      val = x;
    } else {
      val = x % md;
    }
    if (val < 0) {
      val += md;
    }
  }
  int& operator()() { return val; }
  Mint& operator+=(Mint x) {
    if ((val += x.val) > md) {
      val -= md;
    }
    return *this;
  }
  Mint& operator-=(Mint x) {
    if ((val -= x.val) < 0) {
      val += md;
    }
    return *this;
  }
  Mint& operator*=(Mint x) {
    val = int(1LL * val * x.val % md);
    return *this;
  }
};
Mint operator+(Mint x, Mint y) {
  return x += y;
}
Mint operator-(Mint x, Mint y) {
  return x -= y;
}
Mint operator*(Mint x, Mint y) {
  return x *= y;
}
string to_string(Mint x) {
  return to_string(x.val);
}
 
template<typename T>
Mint power(Mint x, T p) {
  Mint res = 1;
  while (p > 0) {
    if (p & 1) {
      res *= x;
    }
    x *= x;
    p >>= 1;
  }
  return res;
}
 
int valid(int N, int inputSeq[])
{
  auto A = inverse_fuck(inputSeq, N);
  int prev = -1;
  for (int i = 0; i < N; ++i) {
    if (A[i] <= N) {
      if (prev != -1) {
        if (i - prev != (A[i] - A[prev] + N) % N) {
          return false;
        }
      }
      prev = i;
    }
  }
  return set<int>(A.begin(), A.end()).size() == A.size();
}
 
//----------------------
 
int replacement(int N, int inputSeq[], int replacementSeq[])
{
  auto A = inverse_fuck(inputSeq, N);
  int mn = min_element(A.begin(), A.end()) - A.begin();
  vector<int> cur(N);
  for (int i = 0; i < N; ++i) {
    cur[(mn + i) % N] = (A[mn] + i - 1) % N + 1;
  }
  
  debug(A, cur);
  int mx = max_element(A.begin(), A.end()) - A.begin();
  vector<int> pos(A[mx] + 1, -1);
  for (int i = 0; i < N; ++i) {
    pos[A[i]] = i;
  }
  debug(pos);
  vector<int> ans;
  for (int i = N + 1; i <= A[mx]; ++i) {
    int use = (pos[i] == -1 ? mx : pos[i]);
    ans.push_back(cur[use]);
    cur[use] = i;
  }
  for (int i = 0; i < int(ans.size()); ++i) {
    replacementSeq[i] = ans[i];
  }
  return int(ans.size());
}
 
//----------------------
 
int countReplacement(int N, int inputSeq[])
{
  auto A = inverse_fuck(inputSeq, N);
  if (!valid(N, inputSeq)) {
    return 0;
  }
  sort(A.begin(), A.end());
  Mint res = 1;
  int prev = N;
  for (int i = 0; i < N; ++i) {
    if (A[i] <= N) {
      continue;
    }
    res *= power(N - i, A[i] - prev - 1);
    prev = A[i];
  }
  if (A[0] > N) {
    res *= N;
  }
  return res();
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 6 ms 2260 KB Output is correct
7 Correct 7 ms 956 KB Output is correct
8 Correct 14 ms 4192 KB Output is correct
9 Correct 3 ms 1492 KB Output is correct
10 Correct 13 ms 4844 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 6 ms 2260 KB Output is correct
7 Correct 7 ms 996 KB Output is correct
8 Correct 14 ms 4140 KB Output is correct
9 Correct 4 ms 1492 KB Output is correct
10 Correct 13 ms 4820 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 3 ms 468 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 7 ms 980 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 292 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 8 ms 1532 KB Output is correct
12 Correct 8 ms 1620 KB Output is correct
13 Correct 9 ms 1744 KB Output is correct
14 Correct 8 ms 1424 KB Output is correct
15 Correct 16 ms 2632 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 26 ms 4556 KB Output is correct
10 Correct 21 ms 3824 KB Output is correct
11 Correct 7 ms 1492 KB Output is correct
12 Correct 9 ms 1876 KB Output is correct
13 Correct 3 ms 692 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 27 ms 4568 KB Output is correct
10 Correct 21 ms 3844 KB Output is correct
11 Correct 7 ms 1596 KB Output is correct
12 Correct 9 ms 1876 KB Output is correct
13 Correct 2 ms 596 KB Output is correct
14 Correct 32 ms 5976 KB Output is correct
15 Correct 37 ms 6700 KB Output is correct
16 Correct 6 ms 1492 KB Output is correct
17 Correct 24 ms 4584 KB Output is correct
18 Correct 13 ms 2688 KB Output is correct