답안 #61754 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
61754	2018-07-26T14:22:50 Z	gusfring	Rope (JOI17_rope)	C++14	45 / 100	55 ms	26780 KB

rope

#include <bits/stdc++.h>
using namespace std;
 
typedef pair<int, int> ii;
const int N = 1000005;
 
int n, m, cnt[N];
int a[N], res[N];
int val[N];
vector<int> p[N];
 
int main() {
	scanf("%d %d", &n, &m);
	if (m == 1 || m > 10){ puts("0"); return 0; }
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]); cnt[a[i]]++, p[a[i]].push_back(i);
	}
	set<ii> s;
	for (int i = 1; i <= m; ++i) s.insert(ii(cnt[i], i));
	for (int i = 1; i <= m; ++i) {
		res[i] = 1e9;
		for (int j = 0; j < 2; ++j) {
			vector<int> go;
			int sum = 0;
			for (int k = 0; k < p[i].size(); ++k) {
				if (p[i][k] % 2 == j) {
					int cur = a[p[i][k] - 1];
					if (p[i][k] > 1 && cur != i) {
						if (++val[cur] == 1) go.push_back(cur);
					}
				}
				else {
					int cur = a[p[i][k] + 1];
					if (p[i][k] < n && cur != i) {
						if (++val[cur] == 1) go.push_back(cur);
					}
				}
			}
			for (int k = 0; k < go.size(); ++k) {
				s.erase(s.find(ii(cnt[go[k]], go[k])));
				s.insert(ii(cnt[go[k]] - val[go[k]], go[k]));
			}
			s.erase(s.find(ii(cnt[i], i)));
			res[i] = min(res[i], n - ((*(--s.end())).first + cnt[i]));
			for (int k = 0; k < go.size(); ++k) {
				s.erase(s.find(ii(cnt[go[k]] - val[go[k]], go[k])));
				s.insert(ii(cnt[go[k]], go[k]));				
			}
			s.insert(ii(cnt[i], i));
			for (int k = 0; k < go.size(); ++k) val[go[k]] = 0;
		}
		printf("%d\n", res[i]);
	}
}

Compilation message

rope.cpp: In function 'int main()':
rope.cpp:25:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int k = 0; k < p[i].size(); ++k) {
                    ~~^~~~~~~~~~~~~
rope.cpp:39:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int k = 0; k < go.size(); ++k) {
                    ~~^~~~~~~~~~~
rope.cpp:45:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int k = 0; k < go.size(); ++k) {
                    ~~^~~~~~~~~~~
rope.cpp:50:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int k = 0; k < go.size(); ++k) val[go[k]] = 0;
                    ~~^~~~~~~~~~~
rope.cpp:24:8: warning: unused variable 'sum' [-Wunused-variable]
    int sum = 0;
        ^~~
rope.cpp:13:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
rope.cpp:16:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]); cnt[a[i]]++, p[a[i]].push_back(i);
   ~~~~~^~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	31 ms	23800 KB	Output is correct
2	Correct	25 ms	23908 KB	Output is correct
3	Correct	25 ms	23936 KB	Output is correct
4	Correct	27 ms	23984 KB	Output is correct
5	Correct	30 ms	23984 KB	Output is correct
6	Correct	38 ms	23984 KB	Output is correct
7	Correct	28 ms	23984 KB	Output is correct
8	Correct	30 ms	23984 KB	Output is correct
9	Correct	29 ms	23984 KB	Output is correct
10	Correct	28 ms	23984 KB	Output is correct
11	Correct	24 ms	23984 KB	Output is correct
12	Correct	25 ms	24096 KB	Output is correct
13	Correct	27 ms	24096 KB	Output is correct
14	Correct	24 ms	24096 KB	Output is correct
15	Correct	29 ms	24096 KB	Output is correct
16	Correct	24 ms	24176 KB	Output is correct
17	Correct	26 ms	24176 KB	Output is correct
18	Correct	27 ms	24176 KB	Output is correct
19	Correct	28 ms	24176 KB	Output is correct
20	Correct	23 ms	24176 KB	Output is correct
21	Correct	26 ms	24176 KB	Output is correct
22	Correct	26 ms	24176 KB	Output is correct
23	Correct	24 ms	24176 KB	Output is correct
24	Correct	27 ms	24176 KB	Output is correct
25	Correct	27 ms	24176 KB	Output is correct
26	Correct	24 ms	24176 KB	Output is correct

Subtask #2
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	31 ms	23800 KB	Output is correct
2	Correct	25 ms	23908 KB	Output is correct
3	Correct	25 ms	23936 KB	Output is correct
4	Correct	27 ms	23984 KB	Output is correct
5	Correct	30 ms	23984 KB	Output is correct
6	Correct	38 ms	23984 KB	Output is correct
7	Correct	28 ms	23984 KB	Output is correct
8	Correct	30 ms	23984 KB	Output is correct
9	Correct	29 ms	23984 KB	Output is correct
10	Correct	28 ms	23984 KB	Output is correct
11	Correct	24 ms	23984 KB	Output is correct
12	Correct	25 ms	24096 KB	Output is correct
13	Correct	27 ms	24096 KB	Output is correct
14	Correct	24 ms	24096 KB	Output is correct
15	Correct	29 ms	24096 KB	Output is correct
16	Correct	24 ms	24176 KB	Output is correct
17	Correct	26 ms	24176 KB	Output is correct
18	Correct	27 ms	24176 KB	Output is correct
19	Correct	28 ms	24176 KB	Output is correct
20	Correct	23 ms	24176 KB	Output is correct
21	Correct	26 ms	24176 KB	Output is correct
22	Correct	26 ms	24176 KB	Output is correct
23	Correct	24 ms	24176 KB	Output is correct
24	Correct	27 ms	24176 KB	Output is correct
25	Correct	27 ms	24176 KB	Output is correct
26	Correct	24 ms	24176 KB	Output is correct
27	Correct	43 ms	25244 KB	Output is correct
28	Correct	47 ms	25388 KB	Output is correct
29	Correct	52 ms	25612 KB	Output is correct
30	Correct	47 ms	25996 KB	Output is correct
31	Correct	44 ms	26200 KB	Output is correct
32	Correct	45 ms	26300 KB	Output is correct
33	Correct	55 ms	26660 KB	Output is correct
34	Correct	41 ms	26780 KB	Output is correct

Subtask #3
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	31 ms	23800 KB	Output is correct
2	Correct	25 ms	23908 KB	Output is correct
3	Correct	25 ms	23936 KB	Output is correct
4	Correct	27 ms	23984 KB	Output is correct
5	Correct	30 ms	23984 KB	Output is correct
6	Correct	38 ms	23984 KB	Output is correct
7	Correct	28 ms	23984 KB	Output is correct
8	Correct	30 ms	23984 KB	Output is correct
9	Correct	29 ms	23984 KB	Output is correct
10	Correct	28 ms	23984 KB	Output is correct
11	Correct	24 ms	23984 KB	Output is correct
12	Correct	25 ms	24096 KB	Output is correct
13	Correct	27 ms	24096 KB	Output is correct
14	Correct	24 ms	24096 KB	Output is correct
15	Correct	29 ms	24096 KB	Output is correct
16	Correct	24 ms	24176 KB	Output is correct
17	Correct	26 ms	24176 KB	Output is correct
18	Correct	27 ms	24176 KB	Output is correct
19	Correct	28 ms	24176 KB	Output is correct
20	Correct	23 ms	24176 KB	Output is correct
21	Correct	26 ms	24176 KB	Output is correct
22	Correct	26 ms	24176 KB	Output is correct
23	Correct	24 ms	24176 KB	Output is correct
24	Correct	27 ms	24176 KB	Output is correct
25	Correct	27 ms	24176 KB	Output is correct
26	Correct	24 ms	24176 KB	Output is correct
27	Correct	43 ms	25244 KB	Output is correct
28	Correct	47 ms	25388 KB	Output is correct
29	Correct	52 ms	25612 KB	Output is correct
30	Correct	47 ms	25996 KB	Output is correct
31	Correct	44 ms	26200 KB	Output is correct
32	Correct	45 ms	26300 KB	Output is correct
33	Correct	55 ms	26660 KB	Output is correct
34	Correct	41 ms	26780 KB	Output is correct
35	Incorrect	27 ms	26780 KB	Output isn't correct
36	Halted	0 ms	0 KB	-

Subtask #4
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	31 ms	23800 KB	Output is correct
2	Correct	25 ms	23908 KB	Output is correct
3	Correct	25 ms	23936 KB	Output is correct
4	Correct	27 ms	23984 KB	Output is correct
5	Correct	30 ms	23984 KB	Output is correct
6	Correct	38 ms	23984 KB	Output is correct
7	Correct	28 ms	23984 KB	Output is correct
8	Correct	30 ms	23984 KB	Output is correct
9	Correct	29 ms	23984 KB	Output is correct
10	Correct	28 ms	23984 KB	Output is correct
11	Correct	24 ms	23984 KB	Output is correct
12	Correct	25 ms	24096 KB	Output is correct
13	Correct	27 ms	24096 KB	Output is correct
14	Correct	24 ms	24096 KB	Output is correct
15	Correct	29 ms	24096 KB	Output is correct
16	Correct	24 ms	24176 KB	Output is correct
17	Correct	26 ms	24176 KB	Output is correct
18	Correct	27 ms	24176 KB	Output is correct
19	Correct	28 ms	24176 KB	Output is correct
20	Correct	23 ms	24176 KB	Output is correct
21	Correct	26 ms	24176 KB	Output is correct
22	Correct	26 ms	24176 KB	Output is correct
23	Correct	24 ms	24176 KB	Output is correct
24	Correct	27 ms	24176 KB	Output is correct
25	Correct	27 ms	24176 KB	Output is correct
26	Correct	24 ms	24176 KB	Output is correct
27	Correct	43 ms	25244 KB	Output is correct
28	Correct	47 ms	25388 KB	Output is correct
29	Correct	52 ms	25612 KB	Output is correct
30	Correct	47 ms	25996 KB	Output is correct
31	Correct	44 ms	26200 KB	Output is correct
32	Correct	45 ms	26300 KB	Output is correct
33	Correct	55 ms	26660 KB	Output is correct
34	Correct	41 ms	26780 KB	Output is correct
35	Incorrect	27 ms	26780 KB	Output isn't correct
36	Halted	0 ms	0 KB	-

Subtask #5
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	31 ms	23800 KB	Output is correct
2	Correct	25 ms	23908 KB	Output is correct
3	Correct	25 ms	23936 KB	Output is correct
4	Correct	27 ms	23984 KB	Output is correct
5	Correct	30 ms	23984 KB	Output is correct
6	Correct	38 ms	23984 KB	Output is correct
7	Correct	28 ms	23984 KB	Output is correct
8	Correct	30 ms	23984 KB	Output is correct
9	Correct	29 ms	23984 KB	Output is correct
10	Correct	28 ms	23984 KB	Output is correct
11	Correct	24 ms	23984 KB	Output is correct
12	Correct	25 ms	24096 KB	Output is correct
13	Correct	27 ms	24096 KB	Output is correct
14	Correct	24 ms	24096 KB	Output is correct
15	Correct	29 ms	24096 KB	Output is correct
16	Correct	24 ms	24176 KB	Output is correct
17	Correct	26 ms	24176 KB	Output is correct
18	Correct	27 ms	24176 KB	Output is correct
19	Correct	28 ms	24176 KB	Output is correct
20	Correct	23 ms	24176 KB	Output is correct
21	Correct	26 ms	24176 KB	Output is correct
22	Correct	26 ms	24176 KB	Output is correct
23	Correct	24 ms	24176 KB	Output is correct
24	Correct	27 ms	24176 KB	Output is correct
25	Correct	27 ms	24176 KB	Output is correct
26	Correct	24 ms	24176 KB	Output is correct
27	Correct	43 ms	25244 KB	Output is correct
28	Correct	47 ms	25388 KB	Output is correct
29	Correct	52 ms	25612 KB	Output is correct
30	Correct	47 ms	25996 KB	Output is correct
31	Correct	44 ms	26200 KB	Output is correct
32	Correct	45 ms	26300 KB	Output is correct
33	Correct	55 ms	26660 KB	Output is correct
34	Correct	41 ms	26780 KB	Output is correct
35	Incorrect	27 ms	26780 KB	Output isn't correct
36	Halted	0 ms	0 KB	-

답안 #61754

Compilation message

Subtask #1 15.0 / 15.0

Subtask #2 30.0 / 30.0

Subtask #3 0 / 10.0

Subtask #4 0 / 25.0

Subtask #5 0 / 20.0

Subtask #1
15.0 / 15.0

Subtask #2
30.0 / 30.0

Subtask #3
0 / 10.0

Subtask #4
0 / 25.0

Subtask #5
0 / 20.0