Submission #996492

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
996492	2024-06-10T17:19:13 Z	Dan4Life	Painting Walls (APIO20_paint)	C++17	0 / 100	987 ms	86100 KB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
 
#define all(a) begin(a),end(a)
#define sz(a) (int)a.size()
#define pb push_back
 
const int mxN = (int)2e4+10; 
const int mxM = (int)2e3+10; 
int n, m, k;
bool work[mxN];
vector<int> c, a;
set<int> b[mxN];

bool has[mxM][mxN], has2[mxM][mxN];

//has[x][y] = if contractor x contains the color used in cell y

bool check(int i){
	for(int x = 0; x < m; x++){
		if(i+m-1-x<n or !x){
			if(has2[x][i]) return true;
		}
		else if(has2[x][i] and has[x-1][i+m-1]) return true;
	}
	return false;
}
 
int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) {
	n = N, m = M, k = K;
	for(auto u : C) c.pb(u);
	for(auto u : A) a.pb(u);
	for(int i = 0; i < m; i++)
		for(auto u : B[i]) b[i].insert(u);
		
	memset(has,0,sizeof(has));
	
	for(int i = 0; i < m; i++)
		for(int j = 0; j < n; j++)
			has[i][j] = has2[i][j] = b[i].count(c[j]);
			
	for(int i = 1; i < m; i++)
		for(int j = 1; j < n; j++)
			has[i][j] &= has[i-1][j-1];
	for(int i = m-2; i>=0; i--)
		for(int j = n-2; j>=0; j--)
			has2[i][j] &= has2[i+1][j+1];
			
	memset(work,0,sizeof(work));
	for(int i = 0; i <= n-m; i++) work[i] = check(i);
	if(!work[0] or !work[n-m]) return -1;
	
	int tot = 1;
	for(int i = 0; i < n-m;){
		int j;
		for(j = i+m; j>=i; j--)
			if(work[j]) break;
		if(j==i) return -1;
		tot++; i = j;
	}
	return tot;
}

Subtask #1
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	40796 KB	Output is correct
2	Correct	6 ms	40796 KB	Output is correct
3	Correct	5 ms	40796 KB	Output is correct
4	Correct	6 ms	40796 KB	Output is correct
5	Correct	6 ms	40796 KB	Output is correct
6	Correct	5 ms	40796 KB	Output is correct
7	Correct	5 ms	40796 KB	Output is correct
8	Correct	5 ms	40792 KB	Output is correct
9	Correct	5 ms	40796 KB	Output is correct
10	Correct	5 ms	40796 KB	Output is correct
11	Correct	5 ms	40796 KB	Output is correct
12	Correct	5 ms	40828 KB	Output is correct
13	Correct	6 ms	44892 KB	Output is correct
14	Correct	7 ms	44888 KB	Output is correct
15	Correct	7 ms	45028 KB	Output is correct
16	Correct	7 ms	44892 KB	Output is correct
17	Correct	6 ms	44892 KB	Output is correct
18	Correct	7 ms	44892 KB	Output is correct
19	Correct	6 ms	44988 KB	Output is correct
20	Correct	7 ms	45020 KB	Output is correct
21	Correct	8 ms	45008 KB	Output is correct
22	Correct	24 ms	50516 KB	Output is correct
23	Correct	25 ms	50512 KB	Output is correct
24	Correct	23 ms	50512 KB	Output is correct
25	Correct	6 ms	41304 KB	Output is correct
26	Correct	8 ms	41308 KB	Output is correct
27	Correct	6 ms	41284 KB	Output is correct
28	Correct	9 ms	41308 KB	Output is correct
29	Correct	7 ms	41308 KB	Output is correct
30	Correct	7 ms	41176 KB	Output is correct
31	Correct	559 ms	81484 KB	Output is correct
32	Correct	558 ms	81488 KB	Output is correct
33	Correct	552 ms	81524 KB	Output is correct
34	Correct	556 ms	81492 KB	Output is correct
35	Correct	554 ms	81484 KB	Output is correct
36	Correct	550 ms	81392 KB	Output is correct
37	Correct	987 ms	85840 KB	Output is correct
38	Correct	949 ms	85896 KB	Output is correct
39	Correct	970 ms	86100 KB	Output is correct
40	Runtime error	41 ms	85192 KB	Execution killed with signal 11
41	Halted	0 ms	0 KB	-

Subtask #2
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	40796 KB	Output is correct
2	Correct	6 ms	40796 KB	Output is correct
3	Correct	5 ms	40796 KB	Output is correct
4	Correct	6 ms	40796 KB	Output is correct
5	Correct	6 ms	40796 KB	Output is correct
6	Correct	5 ms	40796 KB	Output is correct
7	Correct	5 ms	40796 KB	Output is correct
8	Correct	5 ms	40792 KB	Output is correct
9	Correct	5 ms	40796 KB	Output is correct
10	Correct	5 ms	40796 KB	Output is correct
11	Correct	5 ms	40796 KB	Output is correct
12	Correct	5 ms	40828 KB	Output is correct
13	Correct	6 ms	44892 KB	Output is correct
14	Correct	7 ms	44888 KB	Output is correct
15	Correct	7 ms	45028 KB	Output is correct
16	Correct	7 ms	44892 KB	Output is correct
17	Correct	6 ms	44892 KB	Output is correct
18	Correct	7 ms	44892 KB	Output is correct
19	Correct	6 ms	44988 KB	Output is correct
20	Correct	7 ms	45020 KB	Output is correct
21	Correct	8 ms	45008 KB	Output is correct
22	Correct	5 ms	40796 KB	Output is correct
23	Correct	5 ms	40840 KB	Output is correct
24	Correct	5 ms	40796 KB	Output is correct
25	Incorrect	5 ms	40796 KB	Output isn't correct
26	Halted	0 ms	0 KB	-

Subtask #3
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	40796 KB	Output is correct
2	Correct	5 ms	40840 KB	Output is correct
3	Correct	5 ms	40796 KB	Output is correct
4	Correct	6 ms	40796 KB	Output is correct
5	Correct	5 ms	40796 KB	Output is correct
6	Correct	6 ms	40796 KB	Output is correct
7	Correct	6 ms	40796 KB	Output is correct
8	Correct	5 ms	40796 KB	Output is correct
9	Correct	5 ms	40796 KB	Output is correct
10	Correct	5 ms	40792 KB	Output is correct
11	Correct	5 ms	40796 KB	Output is correct
12	Correct	5 ms	40796 KB	Output is correct
13	Correct	5 ms	40796 KB	Output is correct
14	Correct	5 ms	40828 KB	Output is correct
15	Correct	6 ms	44892 KB	Output is correct
16	Correct	7 ms	44888 KB	Output is correct
17	Correct	7 ms	45028 KB	Output is correct
18	Correct	7 ms	44892 KB	Output is correct
19	Correct	6 ms	44892 KB	Output is correct
20	Correct	7 ms	44892 KB	Output is correct
21	Correct	6 ms	44988 KB	Output is correct
22	Correct	7 ms	45020 KB	Output is correct
23	Correct	8 ms	45008 KB	Output is correct
24	Correct	24 ms	50516 KB	Output is correct
25	Correct	25 ms	50512 KB	Output is correct
26	Correct	23 ms	50512 KB	Output is correct
27	Correct	5 ms	40796 KB	Output is correct
28	Incorrect	5 ms	40796 KB	Output isn't correct
29	Halted	0 ms	0 KB	-

Subtask #4
0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	40796 KB	Output is correct
2	Correct	5 ms	40840 KB	Output is correct
3	Correct	5 ms	40796 KB	Output is correct
4	Correct	6 ms	40796 KB	Output is correct
5	Correct	5 ms	40796 KB	Output is correct
6	Correct	6 ms	40796 KB	Output is correct
7	Correct	6 ms	40796 KB	Output is correct
8	Correct	5 ms	40796 KB	Output is correct
9	Correct	5 ms	40796 KB	Output is correct
10	Correct	5 ms	40792 KB	Output is correct
11	Correct	5 ms	40796 KB	Output is correct
12	Correct	5 ms	40796 KB	Output is correct
13	Correct	5 ms	40796 KB	Output is correct
14	Correct	5 ms	40828 KB	Output is correct
15	Correct	6 ms	44892 KB	Output is correct
16	Correct	7 ms	44888 KB	Output is correct
17	Correct	7 ms	45028 KB	Output is correct
18	Correct	7 ms	44892 KB	Output is correct
19	Correct	6 ms	44892 KB	Output is correct
20	Correct	7 ms	44892 KB	Output is correct
21	Correct	6 ms	44988 KB	Output is correct
22	Correct	7 ms	45020 KB	Output is correct
23	Correct	8 ms	45008 KB	Output is correct
24	Correct	24 ms	50516 KB	Output is correct
25	Correct	25 ms	50512 KB	Output is correct
26	Correct	23 ms	50512 KB	Output is correct
27	Correct	6 ms	41304 KB	Output is correct
28	Correct	8 ms	41308 KB	Output is correct
29	Correct	6 ms	41284 KB	Output is correct
30	Correct	9 ms	41308 KB	Output is correct
31	Correct	7 ms	41308 KB	Output is correct
32	Correct	7 ms	41176 KB	Output is correct
33	Correct	559 ms	81484 KB	Output is correct
34	Correct	558 ms	81488 KB	Output is correct
35	Correct	552 ms	81524 KB	Output is correct
36	Correct	556 ms	81492 KB	Output is correct
37	Correct	554 ms	81484 KB	Output is correct
38	Correct	550 ms	81392 KB	Output is correct
39	Correct	987 ms	85840 KB	Output is correct
40	Correct	949 ms	85896 KB	Output is correct
41	Correct	970 ms	86100 KB	Output is correct
42	Correct	5 ms	40796 KB	Output is correct
43	Incorrect	5 ms	40796 KB	Output isn't correct
44	Halted	0 ms	0 KB	-

Subtask #5
0 / 37.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	40796 KB	Output is correct
2	Correct	5 ms	40840 KB	Output is correct
3	Correct	5 ms	40796 KB	Output is correct
4	Correct	6 ms	40796 KB	Output is correct
5	Correct	5 ms	40796 KB	Output is correct
6	Correct	6 ms	40796 KB	Output is correct
7	Correct	6 ms	40796 KB	Output is correct
8	Correct	5 ms	40796 KB	Output is correct
9	Correct	5 ms	40796 KB	Output is correct
10	Correct	5 ms	40792 KB	Output is correct
11	Correct	5 ms	40796 KB	Output is correct
12	Correct	5 ms	40796 KB	Output is correct
13	Correct	5 ms	40796 KB	Output is correct
14	Correct	5 ms	40828 KB	Output is correct
15	Correct	6 ms	44892 KB	Output is correct
16	Correct	7 ms	44888 KB	Output is correct
17	Correct	7 ms	45028 KB	Output is correct
18	Correct	7 ms	44892 KB	Output is correct
19	Correct	6 ms	44892 KB	Output is correct
20	Correct	7 ms	44892 KB	Output is correct
21	Correct	6 ms	44988 KB	Output is correct
22	Correct	7 ms	45020 KB	Output is correct
23	Correct	8 ms	45008 KB	Output is correct
24	Correct	24 ms	50516 KB	Output is correct
25	Correct	25 ms	50512 KB	Output is correct
26	Correct	23 ms	50512 KB	Output is correct
27	Correct	6 ms	41304 KB	Output is correct
28	Correct	8 ms	41308 KB	Output is correct
29	Correct	6 ms	41284 KB	Output is correct
30	Correct	9 ms	41308 KB	Output is correct
31	Correct	7 ms	41308 KB	Output is correct
32	Correct	7 ms	41176 KB	Output is correct
33	Correct	559 ms	81484 KB	Output is correct
34	Correct	558 ms	81488 KB	Output is correct
35	Correct	552 ms	81524 KB	Output is correct
36	Correct	556 ms	81492 KB	Output is correct
37	Correct	554 ms	81484 KB	Output is correct
38	Correct	550 ms	81392 KB	Output is correct
39	Correct	987 ms	85840 KB	Output is correct
40	Correct	949 ms	85896 KB	Output is correct
41	Correct	970 ms	86100 KB	Output is correct
42	Runtime error	41 ms	85192 KB	Execution killed with signal 11
43	Halted	0 ms	0 KB	-

Submission #996492

Compilation message

Subtask #1 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
0 / 12.0

Subtask #2
0 / 15.0

Subtask #3
0 / 13.0

Subtask #4
0 / 23.0

Subtask #5
0 / 37.0