Submission #21592

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
21592	2017-04-15T04:54:59 Z	kingpig9	Arranging Tickets (JOI17_arranging_tickets)	C++11	10 / 100	503 ms	3972 KB

arranging_tickets

#include <bits/stdc++.h>

using namespace std;
const int MAXN = 1e5 + 10;

int N, M;
int A[MAXN], B[MAXN];
int num[MAXN];
int nxt[MAXN], prv[MAXN];

int main() {
	scanf("%d %d", &N, &M);
	for (int i = 0; i < M; i++) {
		scanf("%d %d 1", &A[i], &B[i]);
		A[i]--;
		B[i]--;
	}

	for (int i = 0; i < N; i++) {
		nxt[i] = (i + 1) % N;
		prv[i] = (i + N - 1) % N;
	}

	int ans = 1e9;
	for (int i = 0; i < (1 << M); i++) {
		fill_n(num, N, 0);
		for (int j = 0; j < M; j++) {
			if (i & (1 << j)) {
				for (int k = A[j]; k != B[j]; k = nxt[k]) {
					num[k]++;
				}
			} else {
				for (int k = B[j]; k != A[j]; k = nxt[k]) {
					num[k]++;
				}
			}
		}

		int mx = 0;
		for (int j = 0; j < N; j++) {
			mx = max(mx, num[j]);
		}
		ans = min(ans, mx);
	}
	printf("%d\n", ans);
}

Compilation message

arranging_tickets.cpp: In function 'int main()':
arranging_tickets.cpp:12:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &N, &M);
                        ^
arranging_tickets.cpp:14:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d 1", &A[i], &B[i]);
                                 ^

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	463 ms	3972 KB	Output is correct
2	Correct	473 ms	3972 KB	Output is correct
3	Correct	459 ms	3972 KB	Output is correct
4	Correct	476 ms	3972 KB	Output is correct
5	Correct	503 ms	3972 KB	Output is correct
6	Correct	469 ms	3972 KB	Output is correct
7	Correct	479 ms	3972 KB	Output is correct
8	Correct	476 ms	3972 KB	Output is correct
9	Correct	473 ms	3972 KB	Output is correct
10	Correct	483 ms	3972 KB	Output is correct
11	Correct	463 ms	3972 KB	Output is correct
12	Correct	473 ms	3972 KB	Output is correct
13	Correct	473 ms	3972 KB	Output is correct
14	Correct	469 ms	3972 KB	Output is correct
15	Correct	473 ms	3972 KB	Output is correct

Subtask #2

0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	463 ms	3972 KB	Output is correct
2	Correct	473 ms	3972 KB	Output is correct
3	Correct	459 ms	3972 KB	Output is correct
4	Correct	476 ms	3972 KB	Output is correct
5	Correct	503 ms	3972 KB	Output is correct
6	Correct	469 ms	3972 KB	Output is correct
7	Correct	479 ms	3972 KB	Output is correct
8	Correct	476 ms	3972 KB	Output is correct
9	Correct	473 ms	3972 KB	Output is correct
10	Correct	483 ms	3972 KB	Output is correct
11	Correct	463 ms	3972 KB	Output is correct
12	Correct	473 ms	3972 KB	Output is correct
13	Correct	473 ms	3972 KB	Output is correct
14	Correct	469 ms	3972 KB	Output is correct
15	Correct	473 ms	3972 KB	Output is correct
16	Incorrect	446 ms	3972 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #3

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	463 ms	3972 KB	Output is correct
2	Correct	473 ms	3972 KB	Output is correct
3	Correct	459 ms	3972 KB	Output is correct
4	Correct	476 ms	3972 KB	Output is correct
5	Correct	503 ms	3972 KB	Output is correct
6	Correct	469 ms	3972 KB	Output is correct
7	Correct	479 ms	3972 KB	Output is correct
8	Correct	476 ms	3972 KB	Output is correct
9	Correct	473 ms	3972 KB	Output is correct
10	Correct	483 ms	3972 KB	Output is correct
11	Correct	463 ms	3972 KB	Output is correct
12	Correct	473 ms	3972 KB	Output is correct
13	Correct	473 ms	3972 KB	Output is correct
14	Correct	469 ms	3972 KB	Output is correct
15	Correct	473 ms	3972 KB	Output is correct
16	Incorrect	446 ms	3972 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #4

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	463 ms	3972 KB	Output is correct
2	Correct	473 ms	3972 KB	Output is correct
3	Correct	459 ms	3972 KB	Output is correct
4	Correct	476 ms	3972 KB	Output is correct
5	Correct	503 ms	3972 KB	Output is correct
6	Correct	469 ms	3972 KB	Output is correct
7	Correct	479 ms	3972 KB	Output is correct
8	Correct	476 ms	3972 KB	Output is correct
9	Correct	473 ms	3972 KB	Output is correct
10	Correct	483 ms	3972 KB	Output is correct
11	Correct	463 ms	3972 KB	Output is correct
12	Correct	473 ms	3972 KB	Output is correct
13	Correct	473 ms	3972 KB	Output is correct
14	Correct	469 ms	3972 KB	Output is correct
15	Correct	473 ms	3972 KB	Output is correct
16	Incorrect	446 ms	3972 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #5

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	463 ms	3972 KB	Output is correct
2	Correct	473 ms	3972 KB	Output is correct
3	Correct	459 ms	3972 KB	Output is correct
4	Correct	476 ms	3972 KB	Output is correct
5	Correct	503 ms	3972 KB	Output is correct
6	Correct	469 ms	3972 KB	Output is correct
7	Correct	479 ms	3972 KB	Output is correct
8	Correct	476 ms	3972 KB	Output is correct
9	Correct	473 ms	3972 KB	Output is correct
10	Correct	483 ms	3972 KB	Output is correct
11	Correct	463 ms	3972 KB	Output is correct
12	Correct	473 ms	3972 KB	Output is correct
13	Correct	473 ms	3972 KB	Output is correct
14	Correct	469 ms	3972 KB	Output is correct
15	Correct	473 ms	3972 KB	Output is correct
16	Incorrect	446 ms	3972 KB	Output isn't correct
17	Halted	0 ms	0 KB	-