oj.uz

Submission #217348

# Submission time Handle Problem Language Result Execution time Memory
217348 2020-03-29T13:00:32 Z rama_pang Ruins 3 (JOI20_ruins3) C++14
100 / 100
 1939 ms 14456 KB 
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;

int ADD() { return 0; }
int MUL() { return 1; }

template<typename... Tail> int ADD(int H, Tail... T) {
  return ((H += ADD(T...)) >= MOD) ? H - MOD : H;
}

template<typename...Tail> int MUL(int H, Tail...T) {
  return 1ll * H * MUL(T...) % MOD;
}

const int MAXN = 1205;

int N;
int A[MAXN];
bool is_special[MAXN];

int C[MAXN][MAXN]; // binomial coefficent
int ways[MAXN][MAXN];
int total_ways[MAXN];
int dp[MAXN][MAXN];

void Read() {
  cin >> N;
  for (int i = 1; i <= N; i++) {
    cin >> A[i];
    is_special[A[i]] = true;
  }
}

void InitBinomial() {
  C[0][0] = 1;
  for (int i = 1; i <= 2 * N; i++) {
    for (int j = 0; j <= i; j++) {
      C[i][j] = ADD(C[i - 1][j], (j > 0 ? C[i - 1][j - 1] : 0));
    }
  }
}

void CountWays() {
  for (int l = 1; l <= N; l++) {
    // ways[i][j] = number of ways of choosing and permuting j integers from the set {1, 1, 2, 2, ..., i, i} 
    // (each element appears twice), such that the first element is l, and the following holds: p[i] >= i if 
    // we sort p, where p is the permutation chosen.
    
    ways[0][1] = 2; // the element l is already in the front of the set, of which there are two kinds

    for (int i = 1; i <= N; i++) { // we consider placing element i into the set
      for (int j = 0; j <= i; j++) { // the number of elements that we have picked. 
        // Note that i >= j always holds, and since j is the current position index and i is the element, 
        // p[i] >= i holds when sorted.

        ways[i][j] = 0; // reset

        if (i == l) {
          ways[i][j] = ADD(ways[i][j], ways[i - 1][j]); // we place element l into the front, of which there remains only one kind
          if (j >= 1) {
            ways[i][j] = ADD(ways[i][j], MUL(ways[i - 1][j - 1], j - 1)); // we place one of element l in one of the gaps
          }
        } else {
          ways[i][j] = ADD(ways[i][j], ways[i - 1][j]); // we do not place element i into the set
          if (j >= 1) {
            // We place a single element i into the set. Since we consider two pillars with height i different, 
            // we multiply it by 2. We can place the new element to j positions relative to the elements currently 
            // inside (ways[i - 1] have j - 1 elements, and there are j gaps between these elements that we can 
            // place the new element into). However, because we have already placed element l in the front, we cannot
            // place i in the front, so the possible gaps decrease by 1.
            ways[i][j] = ADD(ways[i][j], MUL(2, ways[i - 1][j - 1], j - 1));
          }
          if (j >= 2)  {
            ways[i][j] = ADD(ways[i][j], MUL(ways[i - 1][j - 2], j - 2, 2)); // we place both elements in the same gap. We can permute the new elements by 2!, so we multiply it by 2.
            ways[i][j] = ADD(ways[i][j], MUL(ways[i - 1][j - 2], j - 2, j - 3)); // we place both elements in different gaps
          }
        }
      }
    }

    for (int i = l; i <= N; i++) {
      total_ways[i] = ADD(total_ways[i], ways[i][i]); // ways[l][k][k] contributes to total_ways[k], since total_ways[k] = sum of ways[l][k][k] for l = 1, 2, ..., k.
    }
  }
}

void CalculateDP() {
  dp[2 * N][0] = 1; // dp[pos][height] = we have placed special pillars of height 1, 2, 3, ..., height and all pillars pos + 1, pos + 2, ..., 2N
  int special = 0, non_special = 0; // count special and non-special positions that we have encountered
  for (int pos = 2 * N; pos >= 1; pos--) {
    if (is_special[pos]) { // now current pillar is special
      for (int new_height = 0; new_height <= N; new_height++) { // new bound
        dp[pos - 1][new_height] = ADD(dp[pos - 1][new_height], dp[pos][new_height]); // we leave the current special pillar slot unfilled
        for (int cur_height = 0; cur_height < min(new_height, special + 1); cur_height++) { 
          // we fill the special pillar slot, and since we have filled exactly cur_height special positions, there are 
          // special - cur_height positions left. Since we add (add) new special pillars, and one of them must be at 
          // current position, we multiply it by C[special - cur_height][add - 1].
          int add = new_height - cur_height;
          dp[pos - 1][new_height] = ADD(dp[pos - 1][new_height], MUL(dp[pos][cur_height], C[special - cur_height][add - 1], total_ways[add])); 
          // we place a special pillar of height cur_height + 1 at the current position, to avoid double counting. 
          // The number of ways to achieve this is total_ways[add] = for all l = 1...add, if we place l at the front, 
          // how many ways are there to get a valid sequence that after earthqueakes, elements 1, 2, ..., add are left, 
          // such that the first element is 1? Since the final height of the first element is 1, it corresponds to
          // the final height of the pillar at the current position as cur_hegiht + 1 (since we are adding pillars with
          // height cur_height + 1, cur_height + 2, ..., final_height).
        }
      }
      special++;
    } else { // current pillar is not special
      for (int j = non_special; j <= special; j++) {
        // we have (j - non_special) pillars we can add without breaking rules (since adding a pillar of new height means 
        // that pillar must be special (and this location is not), we cannot place a new height).
        dp[pos - 1][j] = MUL(dp[pos][j], j - non_special); 
      }
      non_special++;
    }
  }
}

int Answer() {
  int res = dp[0][N];
  for (int i = 0; i < N; i++) {
    if (res & 1) res += MOD;
    res /= 2; // we previoiusly considered 2 pillars with the same height different, but in actuality they are the same. Thus we divide everything by 2^N
  }

  return res;
}

int main() {
  Read();
  
  InitBinomial();
  CountWays();
  CalculateDP();
  
  cout << Answer() << "\n";
  return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Correct 5 ms 640 KB Output is correct
4 Correct 5 ms 512 KB Output is correct
5 Correct 6 ms 640 KB Output is correct
6 Correct 5 ms 640 KB Output is correct
7 Correct 5 ms 640 KB Output is correct
8 Correct 5 ms 640 KB Output is correct
9 Correct 5 ms 640 KB Output is correct
10 Correct 5 ms 640 KB Output is correct

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Correct 5 ms 640 KB Output is correct
4 Correct 5 ms 512 KB Output is correct
5 Correct 6 ms 640 KB Output is correct
6 Correct 5 ms 640 KB Output is correct
7 Correct 5 ms 640 KB Output is correct
8 Correct 5 ms 640 KB Output is correct
9 Correct 5 ms 640 KB Output is correct
10 Correct 5 ms 640 KB Output is correct
11 Correct 7 ms 1536 KB Output is correct
12 Correct 7 ms 1536 KB Output is correct
13 Correct 7 ms 1536 KB Output is correct
14 Correct 7 ms 1536 KB Output is correct
15 Correct 8 ms 1408 KB Output is correct
16 Correct 7 ms 1536 KB Output is correct
17 Correct 7 ms 1408 KB Output is correct
18 Correct 7 ms 1536 KB Output is correct
19 Correct 8 ms 1536 KB Output is correct
20 Correct 9 ms 1536 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Correct 5 ms 640 KB Output is correct
4 Correct 5 ms 512 KB Output is correct
5 Correct 6 ms 640 KB Output is correct
6 Correct 5 ms 640 KB Output is correct
7 Correct 5 ms 640 KB Output is correct
8 Correct 5 ms 640 KB Output is correct
9 Correct 5 ms 640 KB Output is correct
10 Correct 5 ms 640 KB Output is correct
11 Correct 7 ms 1536 KB Output is correct
12 Correct 7 ms 1536 KB Output is correct
13 Correct 7 ms 1536 KB Output is correct
14 Correct 7 ms 1536 KB Output is correct
15 Correct 8 ms 1408 KB Output is correct
16 Correct 7 ms 1536 KB Output is correct
17 Correct 7 ms 1408 KB Output is correct
18 Correct 7 ms 1536 KB Output is correct
19 Correct 8 ms 1536 KB Output is correct
20 Correct 9 ms 1536 KB Output is correct
21 Correct 1906 ms 14304 KB Output is correct
22 Correct 1864 ms 14252 KB Output is correct
23 Correct 1880 ms 14200 KB Output is correct
24 Correct 1878 ms 14328 KB Output is correct
25 Correct 1871 ms 12280 KB Output is correct
26 Correct 1913 ms 14200 KB Output is correct
27 Correct 1892 ms 13432 KB Output is correct
28 Correct 1884 ms 14328 KB Output is correct
29 Correct 1889 ms 11640 KB Output is correct
30 Correct 1860 ms 14328 KB Output is correct
31 Correct 1886 ms 14328 KB Output is correct
32 Correct 1912 ms 14376 KB Output is correct
33 Correct 1880 ms 14328 KB Output is correct
34 Correct 1939 ms 14456 KB Output is correct
35 Correct 1884 ms 14428 KB Output is correct
36 Correct 1931 ms 14456 KB Output is correct