oj.uz

Submission #198435

# Submission time Handle Problem Language Result Execution time Memory
198435 2020-01-26T02:54:23 Z model_code W (RMI18_w) C
15 / 100
 600 ms 504 KB 
/**
 * Method: Naively generates all permutations and counts them.
 *
 * Author: Catalin Francu
 *
 * Restrictions: values must be between 1 and 31.
 *
 * Implementation details:
 *
 * The bkt() function generates all permutations of the input set. To avoid
 * duplicates, at every level it uses each value at most once. It keeps a bit
 * mask to remember the values already used (hence the above restriction).
 *
 * As it progresses, bkt() keeps track of the legality of the permutation so
 * far. It does so with the finite state automaton (STATES) documented below.
 *
 * processSolution() just increments a global counter, but you can compile
 * with -DDEBUG to get a listing of all solutions.
 *
 * There is no need for modular arithmetic. It would take far too long to
 * count 1.000.000.000 solutions.
 **/
#include <stdio.h>

#define MAX_N 100

/* 0 if a < b, 1 if a == b, 2 if a > b */
#define CMP(a, b) (1 + (a > b) - (a < b))

/**
 * states[s][c] = next state if the current state is s and
 * CMP(previous number, current number) = c
 **/
int STATES[6][3] =
  {
   { 5, 0, 1 }, /* 0 = read a bunch of equal numbers, no inequality yet */
   { 2, 1, 1 }, /* 1 = read a smaller number; safe to move on to leg 2 */
   { 2, 2, 3 }, /* 2 = read a larger number; safe to move on to leg 3 */
   { 4, 3, 3 }, /* 3 = read a smaller number; safe to move on to leg 4 */
   { 4, 4, 5 }, /* 4 = read a larger number; safe to end; only final state */
   { 5, 5, 5 }, /* 5 = error state (absorbing) */
  };
#define ACCEPTING_STATE 4
#define ERROR_STATE 5

int v[MAX_N + 1]; /* 1-based so we can test against v[0] without errors */
int n, numSolutions;

void processSolution() {
  numSolutions++;
#ifdef DEBUG
  for (int i = 1; i <= n; i++) {
    printf("%d ", v[i]);
  }
  printf("\n");
#endif
}

void bkt(int level, int state) {
  if (state == ERROR_STATE) {
    return;
  }

  if (level > n) {
    if (state == ACCEPTING_STATE) {
      processSolution();
    }
    return;
  }

  unsigned seen = 0; /* bit mask of already used values */
  for (int i = level; i <= n; i++) {
    if (!(seen & (1 << v[i]))) {
      int tmp = v[i];
      v[i] = v[level];
      v[level] = tmp;

      seen |= (1 << v[level]);
      int cmp = CMP(v[level - 1], v[level]);
      int newState = (level == 1) ? 0 : STATES[state][cmp];
      bkt(level + 1, newState);

      tmp = v[i];
      v[i] = v[level];
      v[level] = tmp;
    }
  }

}

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &v[i]);
  }

  bkt(1, 0);

  printf("%d\n", numSolutions);
}

Compilation message

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

Subtask #1
5.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 256 KB Output is correct
2 Incorrect 53 ms 256 KB Output isn't correct
3 Runtime error 6 ms 376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 5 ms 376 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1090 ms 256 KB Time limit exceeded
2 Execution timed out 1093 ms 256 KB Time limit exceeded
3 Runtime error 6 ms 408 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 6 ms 376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 6 ms 376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 5 ms 376 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #3
10.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 245 ms 256 KB Output is correct
3 Execution timed out 1092 ms 256 KB Time limit exceeded
4 Execution timed out 1094 ms 256 KB Time limit exceeded
5 Runtime error 5 ms 376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 5 ms 376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 5 ms 380 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 6 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 5 ms 376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 5 ms 376 KB Execution killed with signal 11 (could be triggered by violating memory limits)