Submission #741157

#	Time	Username	Problem	Language	Result	Execution time	Memory
741157		rainboy	Travelling Salesperson (CCO20_day2problem1)	C11	25 / 25	441 ms	24280 KiB

Main

#include <stdio.h>
#include <string.h>

#define N	2000

int main() {
	static char cc[N][N + 1];
	static int prev[N], next[N];
	int n, i, j, k, p, q;

	scanf("%d", &n);
	for (i = 1; i < n; i++)
		scanf("%s", cc[i]);
	for (i = 0; i < n; i++)
		for (j = i + 1; j < n; j++)
			cc[i][j] = cc[j][i];
	for (i = 0; i < n; i++) {
		memset(prev, -1, n * sizeof *prev), memset(next, -1, n * sizeof *next);
		prev[i] = next[i] = i;
		for (k = 0, j = i; k < n; k++) {
			if (k == i)
				continue;
			if (j == i)
				next[i] = prev[i] = k, next[k] = prev[k] = i, j = k;
			else {
				p = prev[j], q = next[j];
				if (cc[j][k] == cc[p][j]) {
					next[j] = k, prev[k] = j, next[k] = q, prev[q] = k;
					if (q == i || cc[k][q] != cc[j][k])
						j = k;
					else
						j = q;
				} else {
					prev[j] = k, next[k] = j, prev[k] = p, next[p] = k;
					if (cc[k][p] != cc[j][k])
						j = k;
					else
						j = p == i ? prev[p] : p;
				}
			}
		}
		printf("%d\n", n);
		j = i;
		do {
			printf("%d ", j + 1);
		} while ((j = next[j]) != i);
		printf("\n");
	}
	return 0;
}

Compilation message (stderr)

Main.c: In function 'main':
Main.c:11:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
Main.c:13:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |   scanf("%s", cc[i]);
      |   ^~~~~~~~~~~~~~~~~~

• Subtask 1: 25 / 25