oj.uz

답안 #198434

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
198434 2020-01-26T02:54:19 Z model_code W (RMI18_w) C
30 / 100
 34 ms 2680 KB 
/**
 * Method: Summation by convolution for the case of N distinct elements.
 *
 * Author: Catalin Francu
 **/
#include <stdio.h>

#define MOD 1000000007
#define MAX_N 300000
#define NUM_WAYS 8

const int WAYS[NUM_WAYS][4] =
  {
   { 2, 1, 3, 1 },
   { 2, 1, 3, 2 },
   { 2, 4, 3, 1 },
   { 2, 4, 3, 2 },
   { 2, 4, 3, 1 },
   { 2, 4, 3, 2 },
   { 2, 4, 2, 1 },
   { 2, 4, 2, 1 },
  };

typedef unsigned long long u64;

u64 p[MAX_N];

int main() {
  /* read input data; we only care about n */
  int n;
  scanf("%d", &n);

  u64 result = 0;
  for (int way = 0; way < NUM_WAYS; way++) {
    u64 sum = 1;
    u64 pow = 1;
    for (int i = 2; i < n - 2; i++) {
      /* here i is the current position of C and sum is the number of ways to */
      /* distribute the elements to the left of C */
      p[i] = sum;
      pow = (pow * WAYS[way][1]) % MOD;
      sum = (sum * WAYS[way][0] + pow) % MOD;
    }

    sum = 1;
    pow = 1;
    for (int i = 2; i < n - 2; i++) {
      /* here i is the current position of C, sum is the number of ways to */
      /* distribute the elements to the right of C, and the convolution of p[] */
      /* and sum is added to the final result. */
      result = (result + sum * p[n - 1 - i]) % MOD;
      pow = (pow * WAYS[way][3]) % MOD;
      sum = (sum * WAYS[way][2] + pow) % MOD;
    }
  }

  /* there are 16 states and we handled 8, so take symmetry into account */
  result = result * 2 % MOD;

  printf("%llu\n", result);
}

Compilation message

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

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 256 KB Output isn't correct
2 Incorrect 5 ms 256 KB Output isn't correct
3 Incorrect 10 ms 632 KB Output isn't correct
4 Incorrect 34 ms 2680 KB Output isn't correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 6 ms 256 KB Output is correct
3 Correct 8 ms 504 KB Output is correct
4 Correct 14 ms 1016 KB Output is correct
5 Correct 24 ms 1912 KB Output is correct
6 Correct 33 ms 2680 KB Output is correct

Subtask #3
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 376 KB Output isn't correct
2 Incorrect 5 ms 256 KB Output isn't correct
3 Incorrect 5 ms 256 KB Output isn't correct
4 Incorrect 5 ms 256 KB Output isn't correct
5 Incorrect 5 ms 376 KB Output isn't correct
6 Incorrect 5 ms 376 KB Output isn't correct
7 Incorrect 6 ms 376 KB Output isn't correct
8 Incorrect 14 ms 1020 KB Output isn't correct
9 Incorrect 23 ms 1912 KB Output isn't correct
10 Incorrect 33 ms 2680 KB Output isn't correct