답안 #982408

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
982408	2024-05-14T08:16:30 Z	Der_Vlapos	벽 칠하기 (APIO20_paint)	C++17	12 / 100	106 ms	19212 KB

paint

#include "paint.h"

// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #include <x86intrin.h>

#include <bits/stdc++.h>
#include <chrono>
#include <random>

// @author: Vlapos

namespace operators
{
	template <typename T1, typename T2>
	std::istream &operator>>(std::istream &in, std::pair<T1, T2> &x)
	{
		in >> x.first >> x.second;
		return in;
	}

	template <typename T1, typename T2>
	std::ostream &operator<<(std::ostream &out, std::pair<T1, T2> x)
	{
		out << x.first << " " << x.second;
		return out;
	}

	template <typename T1>
	std::istream &operator>>(std::istream &in, std::vector<T1> &x)
	{
		for (auto &i : x)
			in >> i;
		return in;
	}

	template <typename T1>
	std::ostream &operator<<(std::ostream &out, std::vector<T1> &x)
	{
		for (auto &i : x)
			out << i << " ";
		return out;
	}

	template <typename T1>
	std::ostream &operator<<(std::ostream &out, std::set<T1> &x)
	{
		for (auto &i : x)
			out << i << " ";
		return out;
	}
}

// name spaces
using namespace std;
using namespace operators;
// end of name spaces

// defines
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define f first
#define s second
#define uint unsigned int
#define all(vc) vc.begin(), vc.end()
// end of defines

// usefull stuff

void boost()
{
	ios_base ::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
}

inline int getbit(int &x, int &bt) { return (x >> bt) & 1; }

const int dx4[4] = {-1, 0, 0, 1};
const int dy4[4] = {0, -1, 1, 0};
const int dx8[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
const int dy8[8] = {-1, -0, 1, -1, 1, -1, 0, 1};

const ll INF = (1e18) + 500;
const int BIG = (1e9) * 2 + 100;
const int MAXN = (1e5) + 5;
const int MOD7 = (1e9) + 7;
const int MOD9 = (1e9) + 9;
const uint MODFFT = 998244353;

int minimumInstructions(int N, int M, int K, std::vector<int> C, std::vector<int> A, std::vector<std::vector<int>> B)
{
	int n = N, m = M, k = K;

	vector<vector<int>> col(k);
	map<pii, bool> good;
	for (int i = 0; i < m; ++i)
		for (auto el : B[i])
		{
			col[el].pb(i);
			good[{i, el}];
		}

	vector<int> isGood(n);
	vector<pii> els;
	for (int i = 0; i < n; ++i)
	{
		unordered_map<int, int> isAdded;
		vector<pii> nels;
		int curMaxLen = 0;
		for (auto [el, len] : els)
		{
			isAdded[el] = 0;
			if (good.find({(el + 1) % m, C[i]}) != good.end())
			{
				isAdded[(el + 1) % m] = 1;
				nels.pb({(el + 1) % m, len + 1});
				curMaxLen = max(curMaxLen, len + 1);
			}
		}
		swap(nels, els);

		for (auto el : col[C[i]])
			if (!isAdded[el])
			{
				isAdded[el] = 1;
				els.pb({el, 1});
				curMaxLen = max(curMaxLen, 1);
			}
		assert(els.size() < 700);

		if (curMaxLen >= m)
			isGood[i - m + 1] = 1;
	}

	int pr = 0;
	int curDone = 0;
	int cnt = 0;
	while (curDone < n)
	{
		int curMax = -1;
		for (int i = pr; i <= curDone; ++i)
			if (isGood[i])
				curMax = i;
		if (curMax == -1)
			break;
		cnt++;
		pr = curDone + 1;
		curDone = curMax + m;
	}

	if (curDone < n)
		return -1;
	else
		return cnt;
}

// ////////////////////////////

// #include "paint.h"

// #include <cassert>
// #include <cstdio>

// #include <string>
// #include <vector>

// int main()
// {
// 	int N, M, K;
// 	assert(3 == scanf("%d %d %d", &N, &M, &K));

// 	std::vector<int> C(N);
// 	for (int i = 0; i < N; ++i)
// 	{
// 		assert(1 == scanf("%d", &C[i]));
// 	}

// 	std::vector<int> A(M);
// 	std::vector<std::vector<int>> B(M);
// 	for (int i = 0; i < M; ++i)
// 	{
// 		assert(1 == scanf("%d", &A[i]));
// 		B[i].resize(A[i]);
// 		for (int j = 0; j < A[i]; ++j)
// 		{
// 			assert(1 == scanf("%d", &B[i][j]));
// 		}
// 	}

// 	int minimum_instructions = minimumInstructions(N, M, K, C, A, B);
// 	printf("%d\n", minimum_instructions);

// 	return 0;
// }

Subtask #1
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	1 ms	368 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	1 ms	2652 KB	Output is correct
14	Correct	2 ms	2648 KB	Output is correct
15	Correct	1 ms	2652 KB	Output is correct
16	Correct	2 ms	2796 KB	Output is correct
17	Correct	1 ms	2652 KB	Output is correct
18	Correct	2 ms	2652 KB	Output is correct
19	Correct	2 ms	2908 KB	Output is correct
20	Correct	2 ms	2908 KB	Output is correct
21	Correct	2 ms	2908 KB	Output is correct
22	Correct	36 ms	12944 KB	Output is correct
23	Correct	34 ms	12896 KB	Output is correct
24	Correct	41 ms	12856 KB	Output is correct
25	Correct	4 ms	604 KB	Output is correct
26	Correct	4 ms	672 KB	Output is correct
27	Correct	5 ms	604 KB	Output is correct
28	Correct	4 ms	604 KB	Output is correct
29	Correct	6 ms	604 KB	Output is correct
30	Correct	4 ms	604 KB	Output is correct
31	Correct	14 ms	5124 KB	Output is correct
32	Correct	13 ms	4956 KB	Output is correct
33	Correct	14 ms	4956 KB	Output is correct
34	Correct	14 ms	4956 KB	Output is correct
35	Correct	15 ms	4988 KB	Output is correct
36	Correct	13 ms	4956 KB	Output is correct
37	Correct	53 ms	13084 KB	Output is correct
38	Correct	55 ms	13124 KB	Output is correct
39	Correct	59 ms	13140 KB	Output is correct
40	Correct	15 ms	1372 KB	Output is correct
41	Correct	9 ms	860 KB	Output is correct
42	Correct	29 ms	1608 KB	Output is correct
43	Correct	14 ms	1220 KB	Output is correct
44	Correct	12 ms	936 KB	Output is correct
45	Correct	20 ms	1620 KB	Output is correct
46	Correct	71 ms	17416 KB	Output is correct
47	Correct	37 ms	11168 KB	Output is correct
48	Correct	44 ms	13628 KB	Output is correct
49	Correct	82 ms	15608 KB	Output is correct
50	Correct	77 ms	15500 KB	Output is correct
51	Correct	75 ms	11948 KB	Output is correct
52	Correct	16 ms	1368 KB	Output is correct
53	Correct	16 ms	1372 KB	Output is correct
54	Correct	19 ms	1372 KB	Output is correct
55	Correct	19 ms	1372 KB	Output is correct
56	Correct	19 ms	1600 KB	Output is correct
57	Correct	25 ms	1368 KB	Output is correct
58	Correct	84 ms	19028 KB	Output is correct
59	Correct	74 ms	19024 KB	Output is correct
60	Correct	75 ms	19212 KB	Output is correct
61	Correct	73 ms	18976 KB	Output is correct
62	Correct	80 ms	19028 KB	Output is correct
63	Correct	76 ms	19036 KB	Output is correct
64	Correct	93 ms	18260 KB	Output is correct
65	Correct	106 ms	18236 KB	Output is correct
66	Correct	91 ms	18260 KB	Output is correct

Subtask #2
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	1 ms	368 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	1 ms	2652 KB	Output is correct
14	Correct	2 ms	2648 KB	Output is correct
15	Correct	1 ms	2652 KB	Output is correct
16	Correct	2 ms	2796 KB	Output is correct
17	Correct	1 ms	2652 KB	Output is correct
18	Correct	2 ms	2652 KB	Output is correct
19	Correct	2 ms	2908 KB	Output is correct
20	Correct	2 ms	2908 KB	Output is correct
21	Correct	2 ms	2908 KB	Output is correct
22	Correct	0 ms	344 KB	Output is correct
23	Correct	0 ms	348 KB	Output is correct
24	Correct	1 ms	348 KB	Output is correct
25	Correct	1 ms	348 KB	Output is correct
26	Correct	0 ms	348 KB	Output is correct
27	Correct	1 ms	348 KB	Output is correct
28	Runtime error	1 ms	604 KB	Execution killed with signal 6
29	Halted	0 ms	0 KB	-

Subtask #3
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	1 ms	368 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	1 ms	2652 KB	Output is correct
16	Correct	2 ms	2648 KB	Output is correct
17	Correct	1 ms	2652 KB	Output is correct
18	Correct	2 ms	2796 KB	Output is correct
19	Correct	1 ms	2652 KB	Output is correct
20	Correct	2 ms	2652 KB	Output is correct
21	Correct	2 ms	2908 KB	Output is correct
22	Correct	2 ms	2908 KB	Output is correct
23	Correct	2 ms	2908 KB	Output is correct
24	Correct	36 ms	12944 KB	Output is correct
25	Correct	34 ms	12896 KB	Output is correct
26	Correct	41 ms	12856 KB	Output is correct
27	Correct	1 ms	348 KB	Output is correct
28	Correct	1 ms	348 KB	Output is correct
29	Correct	0 ms	348 KB	Output is correct
30	Correct	1 ms	348 KB	Output is correct
31	Runtime error	1 ms	604 KB	Execution killed with signal 6
32	Halted	0 ms	0 KB	-

Subtask #4
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	1 ms	368 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	1 ms	2652 KB	Output is correct
16	Correct	2 ms	2648 KB	Output is correct
17	Correct	1 ms	2652 KB	Output is correct
18	Correct	2 ms	2796 KB	Output is correct
19	Correct	1 ms	2652 KB	Output is correct
20	Correct	2 ms	2652 KB	Output is correct
21	Correct	2 ms	2908 KB	Output is correct
22	Correct	2 ms	2908 KB	Output is correct
23	Correct	2 ms	2908 KB	Output is correct
24	Correct	36 ms	12944 KB	Output is correct
25	Correct	34 ms	12896 KB	Output is correct
26	Correct	41 ms	12856 KB	Output is correct
27	Correct	4 ms	604 KB	Output is correct
28	Correct	4 ms	672 KB	Output is correct
29	Correct	5 ms	604 KB	Output is correct
30	Correct	4 ms	604 KB	Output is correct
31	Correct	6 ms	604 KB	Output is correct
32	Correct	4 ms	604 KB	Output is correct
33	Correct	14 ms	5124 KB	Output is correct
34	Correct	13 ms	4956 KB	Output is correct
35	Correct	14 ms	4956 KB	Output is correct
36	Correct	14 ms	4956 KB	Output is correct
37	Correct	15 ms	4988 KB	Output is correct
38	Correct	13 ms	4956 KB	Output is correct
39	Correct	53 ms	13084 KB	Output is correct
40	Correct	55 ms	13124 KB	Output is correct
41	Correct	59 ms	13140 KB	Output is correct
42	Correct	1 ms	348 KB	Output is correct
43	Correct	1 ms	348 KB	Output is correct
44	Correct	0 ms	348 KB	Output is correct
45	Correct	1 ms	348 KB	Output is correct
46	Runtime error	1 ms	604 KB	Execution killed with signal 6
47	Halted	0 ms	0 KB	-

Subtask #5
0 / 37.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	1 ms	368 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	1 ms	2652 KB	Output is correct
16	Correct	2 ms	2648 KB	Output is correct
17	Correct	1 ms	2652 KB	Output is correct
18	Correct	2 ms	2796 KB	Output is correct
19	Correct	1 ms	2652 KB	Output is correct
20	Correct	2 ms	2652 KB	Output is correct
21	Correct	2 ms	2908 KB	Output is correct
22	Correct	2 ms	2908 KB	Output is correct
23	Correct	2 ms	2908 KB	Output is correct
24	Correct	36 ms	12944 KB	Output is correct
25	Correct	34 ms	12896 KB	Output is correct
26	Correct	41 ms	12856 KB	Output is correct
27	Correct	4 ms	604 KB	Output is correct
28	Correct	4 ms	672 KB	Output is correct
29	Correct	5 ms	604 KB	Output is correct
30	Correct	4 ms	604 KB	Output is correct
31	Correct	6 ms	604 KB	Output is correct
32	Correct	4 ms	604 KB	Output is correct
33	Correct	14 ms	5124 KB	Output is correct
34	Correct	13 ms	4956 KB	Output is correct
35	Correct	14 ms	4956 KB	Output is correct
36	Correct	14 ms	4956 KB	Output is correct
37	Correct	15 ms	4988 KB	Output is correct
38	Correct	13 ms	4956 KB	Output is correct
39	Correct	53 ms	13084 KB	Output is correct
40	Correct	55 ms	13124 KB	Output is correct
41	Correct	59 ms	13140 KB	Output is correct
42	Correct	15 ms	1372 KB	Output is correct
43	Correct	9 ms	860 KB	Output is correct
44	Correct	29 ms	1608 KB	Output is correct
45	Correct	14 ms	1220 KB	Output is correct
46	Correct	12 ms	936 KB	Output is correct
47	Correct	20 ms	1620 KB	Output is correct
48	Correct	71 ms	17416 KB	Output is correct
49	Correct	37 ms	11168 KB	Output is correct
50	Correct	44 ms	13628 KB	Output is correct
51	Correct	82 ms	15608 KB	Output is correct
52	Correct	77 ms	15500 KB	Output is correct
53	Correct	75 ms	11948 KB	Output is correct
54	Correct	16 ms	1368 KB	Output is correct
55	Correct	16 ms	1372 KB	Output is correct
56	Correct	19 ms	1372 KB	Output is correct
57	Correct	19 ms	1372 KB	Output is correct
58	Correct	19 ms	1600 KB	Output is correct
59	Correct	25 ms	1368 KB	Output is correct
60	Correct	84 ms	19028 KB	Output is correct
61	Correct	74 ms	19024 KB	Output is correct
62	Correct	75 ms	19212 KB	Output is correct
63	Correct	73 ms	18976 KB	Output is correct
64	Correct	80 ms	19028 KB	Output is correct
65	Correct	76 ms	19036 KB	Output is correct
66	Correct	93 ms	18260 KB	Output is correct
67	Correct	106 ms	18236 KB	Output is correct
68	Correct	91 ms	18260 KB	Output is correct
69	Correct	1 ms	348 KB	Output is correct
70	Correct	1 ms	348 KB	Output is correct
71	Correct	0 ms	348 KB	Output is correct
72	Correct	1 ms	348 KB	Output is correct
73	Runtime error	1 ms	604 KB	Execution killed with signal 6
74	Halted	0 ms	0 KB	-

답안 #982408

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 0 / 15.0

Subtask #3 0 / 13.0

Subtask #4 0 / 23.0

Subtask #5 0 / 37.0

Subtask #1
12.0 / 12.0

Subtask #2
0 / 15.0

Subtask #3
0 / 13.0

Subtask #4
0 / 23.0

Subtask #5
0 / 37.0