oj.uz

Submission #198431

# Submission time Handle Problem Language Result Execution time Memory
198431 2020-01-26T02:54:06 Z model_code W (RMI18_w) C
100 / 100
 135 ms 4216 KB 
/**
 * Method: Recurrence relation. Coefficients of the recurrence are defined
 * manually by looking at the state diagram.
 *
 * Author: Catalin Francu
 **/
#include <stdio.h>

#define MAX_VALUE 1000000
#define MOD 1000000007

typedef unsigned long long u64;

typedef struct {
  u64 a, b, c, d, e, f, g, h, i;
} row;
row p, q;

/* frequencies of array elements */
int freq[MAX_VALUE + 1];

/* precomputing this can cut the running time by some 20% */
int choose(int n, int k) {
  switch (k) {
    case 0: return 1;
    case 1: return n;
    case 2: return (u64)n * (n - 1) / 2 % MOD;
    case 3: return (u64)n * (n - 1) * (n - 2) / 6 % MOD;
    default: return 0; /* should be unreachable */
  }
}

/* combinations with repetition: how many ways are there of placing n */
/* identical balls into k non-identical urns? */
int chooseRep(int n, int k) {
  return choose(n + k - 1, k - 1);
}

u64 helper(int value, int newBits, int totalBits, int freq) {
  return (freq >= newBits)
    ? (u64)value * chooseRep(freq - newBits, totalBits)
    : 0;
}

int main() {
  /* read input data; we only care about element frequencies */
  int n, x;
  scanf("%d", &n);
  while (n--) {
    scanf("%d", &x);
    freq[x]++;
  }

  p.a = 1;

  for (int v = 1; v <= MAX_VALUE; v++) {
    if (freq[v]) {

      q.a = 0;
      q.b = (helper(p.a, 1, 1, freq[v]) +
             helper(p.b, 0, 1, freq[v])) % MOD;
      q.c = (helper(p.b, 1, 2, freq[v]) +
             helper(p.c, 0, 2, freq[v])) % MOD;
      q.d = (helper(p.a, 2, 2, freq[v]) +
             helper(p.b * 2, 1, 2, freq[v]) +
             helper(p.d, 0, 2, freq[v])) % MOD;
      q.e = (helper(p.b, 2, 3, freq[v]) +
             helper(p.c, 1, 3, freq[v]) +
             helper(p.d, 1, 3, freq[v]) +
             helper(p.e, 0, 3, freq[v])) % MOD;
      q.f = (helper(p.d, 1, 1, freq[v])) % MOD;
      q.g = (helper(p.d, 2, 2, freq[v]) +
             helper(p.e, 1, 2, freq[v]) +
             helper(p.f, 1, 1, freq[v]) +
             helper(p.g, 0, 1, freq[v])) % MOD;
      q.h = (helper(p.d, 2, 4, freq[v]) +
             helper(p.e * 2, 1, 4, freq[v]) +
             helper(p.h, 0, 4, freq[v])) % MOD;
      q.i = (helper(p.d, 3, 3, freq[v]) +
             helper(p.e * 2, 2, 3, freq[v]) +
             helper(p.f, 2, 2, freq[v]) +
             helper(p.g * 2, 1, 2, freq[v]) +
             helper(p.h, 1, 3, freq[v]) +
             helper(p.i, 0, 2, freq[v])) % MOD;

      p = q;
    }
  }

  printf("%llu\n", p.i);
}

Compilation message

w.c: In function 'main':
w.c:48:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
   ^~~~~~~~~~~~~~~
w.c:50:5: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &x);
     ^~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 256 KB Output is correct
2 Correct 7 ms 256 KB Output is correct
3 Correct 14 ms 256 KB Output is correct
4 Correct 43 ms 248 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 376 KB Output is correct
2 Correct 7 ms 376 KB Output is correct
3 Correct 19 ms 4216 KB Output is correct
4 Correct 42 ms 4216 KB Output is correct
5 Correct 65 ms 2296 KB Output is correct
6 Correct 135 ms 4216 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 376 KB Output is correct
2 Correct 6 ms 256 KB Output is correct
3 Correct 6 ms 256 KB Output is correct
4 Correct 7 ms 376 KB Output is correct
5 Correct 7 ms 256 KB Output is correct
6 Correct 7 ms 376 KB Output is correct
7 Correct 9 ms 636 KB Output is correct
8 Correct 21 ms 632 KB Output is correct
9 Correct 36 ms 504 KB Output is correct
10 Correct 123 ms 4216 KB Output is correct