oj.uz

Submission #799436

# Submission time Handle Problem Language Result Execution time Memory
799436 2023-07-31T14:22:12 Z erray Gondola (IOI14_gondola) C++17
75 / 100
 26 ms 4820 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());
  long long res = 1;
  int prev = N;
  for (int i = 0; i < N; ++i) {
    if (A[i] <= N) {
      continue;
    }
    int p = A[i] - prev - 1;
    long long m = N - i;
    while (p > 0) {
      if (p % 2 == 1) {
        (res *= m) %= md;
      }
      (m *= m) %= md;
      p /= 2;
    }
    //res *= power(N - i, A[i] - prev - 1);
    prev = A[i];
  }
  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 212 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 980 KB Output is correct
8 Correct 14 ms 4228 KB Output is correct
9 Correct 6 ms 1492 KB Output is correct
10 Correct 13 ms 4820 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 956 KB Output is correct
8 Correct 13 ms 4180 KB Output is correct
9 Correct 4 ms 1540 KB Output is correct
10 Correct 12 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 10 ms 952 KB Output is correct

Subtask #4
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 1 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 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 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 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 376 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 11 ms 1532 KB Output is correct
12 Correct 8 ms 1636 KB Output is correct
13 Correct 13 ms 1744 KB Output is correct
14 Correct 7 ms 1448 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 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

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 1 ms 284 KB Output is correct
4 Correct 1 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 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct

Subtask #9
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 4596 KB Output is correct
10 Correct 21 ms 3892 KB Output is correct
11 Correct 10 ms 1524 KB Output is correct
12 Correct 12 ms 1876 KB Output is correct
13 Incorrect 3 ms 596 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #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 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 26 ms 4532 KB Output is correct
10 Correct 21 ms 3796 KB Output is correct
11 Correct 9 ms 1560 KB Output is correct
12 Correct 12 ms 1876 KB Output is correct
13 Incorrect 2 ms 596 KB Output isn't correct
14 Halted 0 ms 0 KB -