oj.uz

Submission #490078

# Submission time Handle Problem Language Result Execution time Memory
490078 2021-11-25T12:50:47 Z rainboy Zagonetka (COI18_zagonetka) C
100 / 100
 85 ms 328 KB 
#include <stdio.h>
#include <string.h>

#define N	100

int n;

int query(int *ii) {
	static int pp[N];
	int i, x;

	printf("query");
	for (i = 0; i < n; i++)
		pp[ii[i]] = i + 1;
	for (i = 0; i < n; i++)
		printf(" %d", pp[i]);
	printf("\n"), fflush(stdout);
	scanf("%d", &x);
	return x;
}

char adj[N][N]; int dd[N];

int main() {
	static int ii[N], aa[N], bb[N];
	int i, j, k, a, b, c;

	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		scanf("%d", &a), a--;
		ii[a] = i;
	}
	for (b = 1; b < n; b++)
		for (a = b - 1, c = b; a >= 0; a--) {
			int tmp;

			tmp = ii[a];
			for (k = a; k < c; k++)
				ii[k] = ii[k + 1];
			ii[c] = tmp;
			if (!query(ii)) {
				tmp = ii[c];
				for (k = c; k > a; k--)
					ii[k] = ii[k - 1];
				ii[a] = tmp;
				adj[ii[a]][ii[c]] = 1;
			} else
				c--;
		}
	for (i = 0; i < n; i++) {
		dd[i] = 0;
		for (j = 0; j < n; j++)
			if (adj[i][j])
				dd[i]++;
	}
	for (a = n - 1; a >= 0; a--) {
		for (j = n - 1; j >= 0; j--)
			if (dd[j] == 0)
				break;
		dd[j] = -1, aa[j] = a;
		for (i = 0; i < n; i++)
			if (adj[i][j])
				dd[i]--;
	}
	for (j = 0; j < n; j++) {
		dd[j] = 0;
		for (i = 0; i < n; i++)
			if (adj[i][j])
				dd[j]++;
	}
	for (a = 0; a < n; a++) {
		for (i = n - 1; i >= 0; i--)
			if (dd[i] == 0)
				break;
		dd[i] = -1, bb[i] = a;
		for (j = 0; j < n; j++)
			if (adj[i][j])
				dd[j]--;
	}
	printf("end\n");
	for (i = 0; i < n; i++)
		printf("%d ", aa[i] + 1);
	printf("\n");
	for (i = 0; i < n; i++)
		printf("%d ", bb[i] + 1);
	printf("\n");
	return 0;
}

Compilation message

zagonetka.c: In function 'query':
zagonetka.c:18:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |  scanf("%d", &x);
      |  ^~~~~~~~~~~~~~~
zagonetka.c: In function 'main':
zagonetka.c:28:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
zagonetka.c:30:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |   scanf("%d", &a), a--;
      |   ^~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 0 ms 200 KB Output is correct
5 Correct 0 ms 200 KB Output is correct
6 Correct 0 ms 200 KB Output is correct
7 Correct 0 ms 200 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 200 KB Output is correct
2 Correct 20 ms 200 KB Output is correct
3 Correct 24 ms 200 KB Output is correct
4 Correct 29 ms 200 KB Output is correct
5 Correct 7 ms 200 KB Output is correct
6 Correct 30 ms 200 KB Output is correct
7 Correct 4 ms 200 KB Output is correct
8 Correct 6 ms 200 KB Output is correct
9 Correct 22 ms 200 KB Output is correct
10 Correct 15 ms 200 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Output is correct
2 Correct 3 ms 200 KB Output is correct
3 Correct 6 ms 200 KB Output is correct
4 Correct 6 ms 200 KB Output is correct
5 Correct 3 ms 200 KB Output is correct
6 Correct 4 ms 200 KB Output is correct
7 Correct 5 ms 200 KB Output is correct
8 Correct 5 ms 200 KB Output is correct
9 Correct 4 ms 200 KB Output is correct
10 Correct 3 ms 200 KB Output is correct
11 Correct 5 ms 200 KB Output is correct
12 Correct 5 ms 200 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 264 KB Output is correct
2 Correct 74 ms 200 KB Output is correct
3 Correct 64 ms 200 KB Output is correct
4 Correct 71 ms 200 KB Output is correct
5 Correct 85 ms 200 KB Output is correct
6 Correct 80 ms 200 KB Output is correct
7 Correct 63 ms 328 KB Output is correct
8 Correct 58 ms 200 KB Output is correct
9 Correct 63 ms 200 KB Output is correct
10 Correct 52 ms 284 KB Output is correct
11 Correct 70 ms 284 KB Output is correct
12 Correct 65 ms 200 KB Output is correct
13 Correct 72 ms 200 KB Output is correct
14 Correct 52 ms 272 KB Output is correct
15 Correct 73 ms 200 KB Output is correct
16 Correct 65 ms 288 KB Output is correct