oj.uz

Submission #469588

# Submission time Handle Problem Language Result Execution time Memory
469588 2021-09-01T11:44:08 Z Soumya1 Gondola (IOI14_gondola) C++17
60 / 100
 48 ms 4556 KB 
#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
int valid(int n, int a[]) {
  bool ok = true;
  map<int, bool> mp;
  for (int i = 0; i < n; i++) {
    ok &= (!mp[a[i]]);
    mp[a[i]] = true;
  }
  int pos = -1, val = -1;
  for (int i = 0; i < n; i++) {
    if (a[i] <= n) {
      val = a[i];
      pos = i;
      break;
    }
  }
  val++;
  if (val > n) val = 1;
  for (int i = pos + 1; i < n; i++) {
    if (a[i] <= n) {
      ok &= (a[i] == val);
    }
    val++;
    if (val > n) val = 1;
  }
  for (int i = 0; i < pos; i++) {
    if (a[i] <= n) {
      ok &= (a[i] == val);
    }
    val++;
    if (val > n) val = 1;
  }
  return (int) ok;
}
int replacement(int n, int a[], int ans[]) {
  int pos = -1, val = -1;
  for (int i = 0; i < n; i++) {
    if (a[i] <= n) {
      pos = i;
      val = a[i];
      break;
    }
  }
  vector<pair<int, int>> v;
  for (int i = 0; i < n; i++) {
    if (a[i] > n) v.push_back({a[i], i});
  }
  if (pos != -1) {
    for (int i = pos; i < n; i++) {
      a[i] = val++;
      if (val > n) val = 1;
    }
    for (int i = 0; i < pos; i++) {
      a[i] = val++;
      if (val > n) val = 1;
    }
  } else {
    for (int i = 0; i < n; i++) a[i] = i + 1;
  }
  int ptr = 0;
  sort(v.begin(), v.end());
  int cur = n + 1;
  for (int i = 0; i < v.size(); i++) {
    while (cur <= v[i].first) {
      ans[ptr++] = a[v[i].second];
      a[v[i].second] = cur++;
    }
  }
  return ptr;
}
int bigmod(int a, int b) {
  int res = 1;
  while (b > 0) {
    if (b & 1) res = (1LL * res * a) % mod;
    a = (1LL * a * a) % mod, b >>= 1;
  }
  return res;
}
int countReplacement(int n, int a[]) {
  if (!valid(n, a)) return 0;
  int pos = -1, val = -1;
  for (int i = 0; i < n; i++) {
    if (a[i] <= n) {
      pos = i;
      val = a[i];
      break;
    }
  }
  sort(a, a + n);
  int ans = 1;
  int last = n;
  int nn = n;
  for (int i = 0; i < n; i++) {
    if (a[i] > n) {
      ans = (1LL * ans * bigmod(nn, a[i] - last - 1)) % mod;
      last = a[i];
    }
    nn--;
  }
  if (pos == -1) {
    for (int i = 1; i <= n; i++) {
      ans = (1LL * ans * i) % mod;
    }
  }
  return ans;
}

Compilation message

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:66:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |   for (int i = 0; i < v.size(); i++) {
      |                   ~~^~~~~~~~~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:84:17: warning: variable 'val' set but not used [-Wunused-but-set-variable]
   84 |   int pos = -1, val = -1;
      |                 ^~~

Subtask #1
5.0 / 5.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 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct

Subtask #2
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 0 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 15 ms 2124 KB Output is correct
7 Correct 38 ms 3568 KB Output is correct
8 Correct 30 ms 3864 KB Output is correct
9 Correct 9 ms 1400 KB Output is correct
10 Correct 35 ms 4452 KB Output is correct

Subtask #3
10.0 / 10.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 0 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 21 ms 2132 KB Output is correct
7 Correct 48 ms 3548 KB Output is correct
8 Correct 38 ms 3908 KB Output is correct
9 Correct 9 ms 1408 KB Output is correct
10 Correct 35 ms 4444 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 19 ms 2040 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 48 ms 4556 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 1 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

Subtask #5
10.0 / 10.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 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 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 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 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 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
11 Correct 10 ms 588 KB Output is correct
12 Correct 11 ms 624 KB Output is correct
13 Correct 16 ms 1244 KB Output is correct
14 Correct 9 ms 532 KB Output is correct
15 Correct 26 ms 2196 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 0 ms 204 KB Output is correct

Subtask #8
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 0 ms 204 KB Output is correct
6 Correct 1 ms 296 KB Output is correct
7 Incorrect 0 ms 204 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 15.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 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Incorrect 1 ms 204 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #10
0 / 10.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 0 ms 204 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Incorrect 1 ms 204 KB Output isn't correct
8 Halted 0 ms 0 KB -