oj.uz

Submission #528914

# Submission time Handle Problem Language Result Execution time Memory
528914 2022-02-21T18:04:56 Z Alex_tz307 Gondola (IOI14_gondola) C++17
100 / 100
 56 ms 112492 KB 
#include <bits/stdc++.h>
#include "gondola.h"

using namespace std;

int valid(int n, int a[]) {
  int N = 0;
  for (int i = 0; i < n; ++i) {
    N = max(N, a[i]);
  }
  vector<bool> ap(N + 1);
  int pos = 0;
  for (int i = 0; i < n; ++i) {
    if (ap[a[i]]) {
      return 0;
    }
    ap[a[i]] = true;
    if (a[i] < a[pos]) {
      pos = i;
    }
  }
  if (a[pos] > n) {
    return 1;
  }
  int x = a[pos];
  for (int rep = 0; rep < n; ++rep) {
    if (a[pos] <= n && a[pos] != x) {
      return 0;
    }
    x += 1;
    if (x == n + 1) {
      x = 1;
    }
    pos += 1;
    if (pos == n) {
      pos = 0;
    }
  }
  return 1;
}

void maxSelf(int &x, int y) {
  if (x < y) {
    x = y;
  }
}

int replacement(int n, int a[], int sol[]) {
  vector<int> v(n);
  iota(v.begin(), v.end(), 1);
  for (int i = 0; i < n; ++i) {
    if (a[i] <= n) {
      int x = a[i];
      for (int rep = 0; rep < n; ++rep) {
        v[i] = x;
        x += 1;
        if (x == n + 1) {
          x = 1;
        }
        i += 1;
        if (i == n) {
          i = 0;
        }
      }
      break;
    }
  }
  int N = 0;
  for (int i = 0; i < n; ++i) {
    maxSelf(N, a[i]);
  }
  vector<int> w(N + 1);
  for (int i = 0; i < n; ++i) {
    w[a[i]] = v[i];
  }
  int len = 0, x = n + 1;
  for (int i = 1; i <= N; ++i) {
    if (w[i]) {
      while (w[i] < i) {
        sol[len++] = w[i];
        w[i] = x;
        x += 1;
      }
    }
  }
  return len;
}

const int mod = 1e9 + 9;

void multSelf(int &x, const int &y) {
  x = (int64_t)x * y % mod;
}

int Pow(int x, int n) {
  int ans = 1;
  while (n) {
    if (n & 1) {
      multSelf(ans, x);
    }
    multSelf(x, x);
    n >>= 1;
  }
  return ans;
}

int countReplacement(int n, int a[]) {
  if (!valid(n, a)) {
    return 0;
  }
  vector<int> v{n};
  for (int i = 0; i < n; ++i) {
    if (a[i] > n) {
      v.emplace_back(a[i]);
    }
  }
  sort(v.begin(), v.end());
  int ans = 1, m = v.size();
  for (int i = 1; i < m; ++i) {
    multSelf(ans, Pow(m - i, v[i] - v[i - 1] - 1));
  }
  if (m == n + 1) {
    multSelf(ans, n);
  }
  return ans;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 3 ms 332 KB Output is correct
7 Correct 8 ms 588 KB Output is correct
8 Correct 12 ms 520 KB Output is correct
9 Correct 3 ms 332 KB Output is correct
10 Correct 7 ms 632 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 3 ms 452 KB Output is correct
7 Correct 12 ms 528 KB Output is correct
8 Correct 8 ms 588 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 9 ms 524 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 3 ms 460 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 8 ms 588 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 7 ms 1192 KB Output is correct
12 Correct 7 ms 1356 KB Output is correct
13 Correct 10 ms 1260 KB Output is correct
14 Correct 7 ms 1228 KB Output is correct
15 Correct 22 ms 2120 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 296 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 13 ms 1364 KB Output is correct
10 Correct 17 ms 1316 KB Output is correct
11 Correct 7 ms 752 KB Output is correct
12 Correct 8 ms 716 KB Output is correct
13 Correct 2 ms 332 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 300 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 14 ms 1356 KB Output is correct
10 Correct 10 ms 1192 KB Output is correct
11 Correct 4 ms 736 KB Output is correct
12 Correct 5 ms 692 KB Output is correct
13 Correct 2 ms 304 KB Output is correct
14 Correct 56 ms 112492 KB Output is correct
15 Correct 38 ms 55880 KB Output is correct
16 Correct 26 ms 57388 KB Output is correct
17 Correct 27 ms 33100 KB Output is correct
18 Correct 16 ms 16108 KB Output is correct