Submission #21592

#	Time	Username	Problem	Language	Result	Execution time	Memory
21592		kingpig9	Arranging Tickets (JOI17_arranging_tickets)	C++11	10 / 100	503 ms	3972 KiB

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 (stderr)

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 / 10
• Subtask 2: 0 / 35
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 15