oj.uz

Submission #436783

# Submission time Handle Problem Language Result Execution time Memory
436783 2021-06-24T22:07:38 Z Tangent Gondola (IOI14_gondola) C++17
100 / 100
 68 ms 5912 KB 
#include "gondola.h"
#include "bits/stdc++.h"
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vii;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vii> vvii;
typedef vector<vll> vvll;
typedef vector<vpii> vvpii;
typedef vector<vpll> vvpll;
 
#define ffor(i, a, b) for (ll i = (a); i < (ll)(b); i++)
#define fford(i, a, b) for (ll i = (a); i > (ll)(b); i--)
#define rep(i, n) ffor(i, 0, n)
#define forin(x, a) for (auto &x: a)
#define all(a) a.begin(), a.end()

int valid(int n, int s[]) {
  int original = -1;
  map<int, int> counts;
  rep(i, n) {
    if (s[i] < 1) return 0;
    if (counts[s[i]]) return 0;
    counts[s[i]] = 1;
    if (s[i] <= n) {
      if (original == -1) {
        original = i;
      } else {
        if ((i + s[original]) % n != (s[i] + original) % n) {
          return 0;
        }
      }
    }
  }
  return 1;
}

//----------------------

int replacement(int n, int s[], int r[])
{
  vpii changed;
  int offset = 0;
  rep(i, n) {
    if (s[i] > n) {
      changed.emplace_back(s[i], i);
    } else {
      offset = (s[i] - i - 1 + n) % n;
    }
  }
  sort(all(changed));
  int curr = n;
  forin(change, changed) {
    int val = (change.second + offset) % n + 1;
    while (curr < change.first) {
      r[curr++ - n] = val;
      val = curr;
    }
  }
  return curr - n;
}

//----------------------

const int mod = 1000000009;

ll modpow(ll a, ll b) {
  ll curr = a;
  ll res = 1;
  while(b) {
    if (b % 2) {
      res *= curr;
      res %= mod;
    }
    curr *= curr;
    curr %= mod;
    b /= 2;
  }
  return res;
}

int countReplacement(int n, int s[])
{
  if (!valid(n, s)) return 0;
  ll res = 1;
  vii changed;
  bool original = false;
  rep(i, n) {
    if (s[i] > n) {
      changed.emplace_back(s[i]);
    } else {
      original = true;
    }
  }
  sort(all(changed));
  if (!original) res = n;
  int last = n;
  vii diffs;
  forin(change, changed) {
    diffs.emplace_back(change - last - 1);
    last = change;
  }
  reverse(all(diffs));
  rep(i, diffs.size()) {
    res *= modpow(i + 1, diffs[i]);
    res %= mod;
  }

  return (int)res;
}

Subtask #1
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 204 KB Output is correct
4 Correct 1 ms 204 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 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 1 ms 316 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 15 ms 2132 KB Output is correct
7 Correct 10 ms 540 KB Output is correct
8 Correct 35 ms 3812 KB Output is correct
9 Correct 9 ms 1356 KB Output is correct
10 Correct 37 ms 4472 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 1 ms 204 KB Output is correct
4 Correct 1 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 10 ms 588 KB Output is correct
8 Correct 31 ms 3864 KB Output is correct
9 Correct 10 ms 1452 KB Output is correct
10 Correct 35 ms 4448 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 5 ms 460 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 10 ms 644 KB Output is correct

Subtask #4
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 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 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 1 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 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 1 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 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 14 ms 588 KB Output is correct
12 Correct 13 ms 604 KB Output is correct
13 Correct 15 ms 1164 KB Output is correct
14 Correct 9 ms 544 KB Output is correct
15 Correct 23 ms 2116 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 204 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 204 KB Output is correct
4 Correct 1 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 300 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 1 ms 304 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 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 204 KB Output is correct
9 Correct 46 ms 4408 KB Output is correct
10 Correct 37 ms 3676 KB Output is correct
11 Correct 14 ms 1484 KB Output is correct
12 Correct 17 ms 1848 KB Output is correct
13 Correct 5 ms 716 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 1 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 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 204 KB Output is correct
9 Correct 50 ms 4512 KB Output is correct
10 Correct 38 ms 3692 KB Output is correct
11 Correct 13 ms 1484 KB Output is correct
12 Correct 17 ms 1868 KB Output is correct
13 Correct 4 ms 588 KB Output is correct
14 Correct 60 ms 5312 KB Output is correct
15 Correct 68 ms 5912 KB Output is correct
16 Correct 11 ms 1356 KB Output is correct
17 Correct 43 ms 4040 KB Output is correct
18 Correct 23 ms 2372 KB Output is correct