Submission #125282

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
125282	2019-07-05T04:09:45 Z	조승현(#3064)	Arranging Tickets (JOI17_arranging_tickets)	C++14	45 / 100	1865 ms	504 KB

arranging_tickets

#include<cstdio>
#include<algorithm>
using namespace std;
int n, m, C[3010], S[3010], CK[3010];
struct point {
	int a, b;
}w[3010];
bool Pos(int K) {
	int i, j;
	for (i = 1; i <= n; i++)C[i] = 0;
	for (i = 1; i <= m; i++) {
		CK[i] = 0;
		for (j = w[i].a; j < w[i].b; j++)C[j]++;
	}
	for (j = 0; j < 50000000 / max(n, m); j++) {
		int Mx = 0, ss = 0;
		S[0] = 0;
		for (i = 1; i <= n; i++) {
			S[i] = S[i - 1] + (C[i] >= K);
			ss += (C[i] > K);
		}
		if (ss == 0)return true;
		int MM = -1, pv = -1;
		for (i = 1; i <= m; i++) {
			int t = S[w[i].b - 1] - S[w[i].a - 1];
			if (CK[i])t = S[n] - t;
			if (MM < t)MM = t, pv = i;
		}
		for (i = 1; i <= n; i++) {
			if ((CK[pv] == 0) == (w[pv].a <= i && i < w[pv].b)) C[i]--;
			else C[i]++;
		}
		CK[pv] ^= 1;
	}
	return false;
}
int main() {
	int i, j;
	scanf("%d%d", &n, &m);
	if (n > 3000 || m > 3000)return 0;
	for (i = 1; i <= m; i++) {
		int t;
		scanf("%d%d%d", &w[i].a, &w[i].b, &t);
		if (w[i].a > w[i].b)swap(w[i].a, w[i].b);
	}
	int res = 1e9;
	int b = 1, e = m, mid, r;
	while (b <= e) {
		mid = (b + e) >> 1;
		if (Pos(mid)) {
			r = mid;
			e = mid - 1;
		}
		else b = mid + 1;
	}
	printf("%d\n", r);
}

Compilation message

arranging_tickets.cpp: In function 'int main()':
arranging_tickets.cpp:39:7: 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:43:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &w[i].a, &w[i].b, &t);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	866 ms	376 KB	Output is correct
2	Correct	849 ms	376 KB	Output is correct
3	Correct	866 ms	476 KB	Output is correct
4	Correct	878 ms	376 KB	Output is correct
5	Correct	844 ms	376 KB	Output is correct
6	Correct	1121 ms	376 KB	Output is correct
7	Correct	1168 ms	376 KB	Output is correct
8	Correct	847 ms	376 KB	Output is correct
9	Correct	814 ms	376 KB	Output is correct
10	Correct	836 ms	504 KB	Output is correct
11	Correct	1120 ms	356 KB	Output is correct
12	Correct	560 ms	356 KB	Output is correct
13	Correct	868 ms	256 KB	Output is correct
14	Correct	543 ms	376 KB	Output is correct
15	Correct	840 ms	376 KB	Output is correct

Subtask #2
35.0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	866 ms	376 KB	Output is correct
2	Correct	849 ms	376 KB	Output is correct
3	Correct	866 ms	476 KB	Output is correct
4	Correct	878 ms	376 KB	Output is correct
5	Correct	844 ms	376 KB	Output is correct
6	Correct	1121 ms	376 KB	Output is correct
7	Correct	1168 ms	376 KB	Output is correct
8	Correct	847 ms	376 KB	Output is correct
9	Correct	814 ms	376 KB	Output is correct
10	Correct	836 ms	504 KB	Output is correct
11	Correct	1120 ms	356 KB	Output is correct
12	Correct	560 ms	356 KB	Output is correct
13	Correct	868 ms	256 KB	Output is correct
14	Correct	543 ms	376 KB	Output is correct
15	Correct	840 ms	376 KB	Output is correct
16	Correct	1309 ms	376 KB	Output is correct
17	Correct	1319 ms	376 KB	Output is correct
18	Correct	1057 ms	256 KB	Output is correct
19	Correct	1574 ms	376 KB	Output is correct
20	Correct	1089 ms	376 KB	Output is correct
21	Correct	1334 ms	376 KB	Output is correct
22	Correct	1328 ms	252 KB	Output is correct
23	Correct	802 ms	504 KB	Output is correct
24	Correct	1349 ms	360 KB	Output is correct
25	Correct	1865 ms	356 KB	Output is correct
26	Correct	1038 ms	376 KB	Output is correct
27	Correct	1111 ms	376 KB	Output is correct

Subtask #3
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	866 ms	376 KB	Output is correct
2	Correct	849 ms	376 KB	Output is correct
3	Correct	866 ms	476 KB	Output is correct
4	Correct	878 ms	376 KB	Output is correct
5	Correct	844 ms	376 KB	Output is correct
6	Correct	1121 ms	376 KB	Output is correct
7	Correct	1168 ms	376 KB	Output is correct
8	Correct	847 ms	376 KB	Output is correct
9	Correct	814 ms	376 KB	Output is correct
10	Correct	836 ms	504 KB	Output is correct
11	Correct	1120 ms	356 KB	Output is correct
12	Correct	560 ms	356 KB	Output is correct
13	Correct	868 ms	256 KB	Output is correct
14	Correct	543 ms	376 KB	Output is correct
15	Correct	840 ms	376 KB	Output is correct
16	Correct	1309 ms	376 KB	Output is correct
17	Correct	1319 ms	376 KB	Output is correct
18	Correct	1057 ms	256 KB	Output is correct
19	Correct	1574 ms	376 KB	Output is correct
20	Correct	1089 ms	376 KB	Output is correct
21	Correct	1334 ms	376 KB	Output is correct
22	Correct	1328 ms	252 KB	Output is correct
23	Correct	802 ms	504 KB	Output is correct
24	Correct	1349 ms	360 KB	Output is correct
25	Correct	1865 ms	356 KB	Output is correct
26	Correct	1038 ms	376 KB	Output is correct
27	Correct	1111 ms	376 KB	Output is correct
28	Incorrect	1393 ms	436 KB	Output isn't correct
29	Halted	0 ms	0 KB	-

Subtask #4
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	866 ms	376 KB	Output is correct
2	Correct	849 ms	376 KB	Output is correct
3	Correct	866 ms	476 KB	Output is correct
4	Correct	878 ms	376 KB	Output is correct
5	Correct	844 ms	376 KB	Output is correct
6	Correct	1121 ms	376 KB	Output is correct
7	Correct	1168 ms	376 KB	Output is correct
8	Correct	847 ms	376 KB	Output is correct
9	Correct	814 ms	376 KB	Output is correct
10	Correct	836 ms	504 KB	Output is correct
11	Correct	1120 ms	356 KB	Output is correct
12	Correct	560 ms	356 KB	Output is correct
13	Correct	868 ms	256 KB	Output is correct
14	Correct	543 ms	376 KB	Output is correct
15	Correct	840 ms	376 KB	Output is correct
16	Correct	1309 ms	376 KB	Output is correct
17	Correct	1319 ms	376 KB	Output is correct
18	Correct	1057 ms	256 KB	Output is correct
19	Correct	1574 ms	376 KB	Output is correct
20	Correct	1089 ms	376 KB	Output is correct
21	Correct	1334 ms	376 KB	Output is correct
22	Correct	1328 ms	252 KB	Output is correct
23	Correct	802 ms	504 KB	Output is correct
24	Correct	1349 ms	360 KB	Output is correct
25	Correct	1865 ms	356 KB	Output is correct
26	Correct	1038 ms	376 KB	Output is correct
27	Correct	1111 ms	376 KB	Output is correct
28	Incorrect	1393 ms	436 KB	Output isn't correct
29	Halted	0 ms	0 KB	-

Subtask #5
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	866 ms	376 KB	Output is correct
2	Correct	849 ms	376 KB	Output is correct
3	Correct	866 ms	476 KB	Output is correct
4	Correct	878 ms	376 KB	Output is correct
5	Correct	844 ms	376 KB	Output is correct
6	Correct	1121 ms	376 KB	Output is correct
7	Correct	1168 ms	376 KB	Output is correct
8	Correct	847 ms	376 KB	Output is correct
9	Correct	814 ms	376 KB	Output is correct
10	Correct	836 ms	504 KB	Output is correct
11	Correct	1120 ms	356 KB	Output is correct
12	Correct	560 ms	356 KB	Output is correct
13	Correct	868 ms	256 KB	Output is correct
14	Correct	543 ms	376 KB	Output is correct
15	Correct	840 ms	376 KB	Output is correct
16	Correct	1309 ms	376 KB	Output is correct
17	Correct	1319 ms	376 KB	Output is correct
18	Correct	1057 ms	256 KB	Output is correct
19	Correct	1574 ms	376 KB	Output is correct
20	Correct	1089 ms	376 KB	Output is correct
21	Correct	1334 ms	376 KB	Output is correct
22	Correct	1328 ms	252 KB	Output is correct
23	Correct	802 ms	504 KB	Output is correct
24	Correct	1349 ms	360 KB	Output is correct
25	Correct	1865 ms	356 KB	Output is correct
26	Correct	1038 ms	376 KB	Output is correct
27	Correct	1111 ms	376 KB	Output is correct
28	Incorrect	1393 ms	436 KB	Output isn't correct
29	Halted	0 ms	0 KB	-

Submission #125282

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 35.0 / 35.0

Subtask #3 0 / 20.0

Subtask #4 0 / 20.0

Subtask #5 0 / 15.0

Subtask #1
10.0 / 10.0

Subtask #2
35.0 / 35.0

Subtask #3
0 / 20.0

Subtask #4
0 / 20.0

Subtask #5
0 / 15.0