Submission #1021570

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1021570	2024-07-12T19:57:43 Z	MohamedFaresNebili	Painting Walls (APIO20_paint)	C++14	0 / 100	1500 ms	5212 KB

paint

#include <bits/stdc++.h>
     
        using namespace std;

        int N, M, K;
        vector<int> C, A;
        vector<vector<int>> B;
        vector<int> adj[100005];
        map<int, int> Key[50005];

        int solve(int i) {
            if(i >= N) return 0;
            int best = 1e9 + 7; 
            for(auto u : adj[C[i]]) {
                bool ok = true;
                for(int l = 0; l < M; l++) {
                    int col = (u + l) % M;
                    ok &= (Key[col][C[i + l]] == 1);
                }
                if(!ok) continue;
                for(int l = 0; l < M; l++)
                    best = min(best, 1 + solve(i + l + 1));
            }
            return best;
        }

        int minimumInstructions(int _N, int _M, int _K, vector<int> _C, vector<int> _A, vector<vector<int>> _B) {
            N = _N, M = _M, K = _K;
            swap(_C, C); swap(_A, A); swap(_B, B);
            for(int l = 0; l < M; l++) {
                for(int i = 0; i < A[l]; i++) {
                    adj[B[l][i]].push_back(l);
                    Key[l][B[l][i]] = 1;
                }
            }
            int res = solve(0);
            return (res == 1e9 + 7 ? -1 : res);
            return -1;
        }

Subtask #1

0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	4956 KB	Output is correct
2	Correct	3 ms	4956 KB	Output is correct
3	Correct	3 ms	4956 KB	Output is correct
4	Correct	3 ms	4956 KB	Output is correct
5	Correct	3 ms	4956 KB	Output is correct
6	Correct	3 ms	4956 KB	Output is correct
7	Correct	2 ms	4956 KB	Output is correct
8	Correct	4 ms	4956 KB	Output is correct
9	Correct	3 ms	5000 KB	Output is correct
10	Correct	3 ms	4956 KB	Output is correct
11	Correct	2 ms	4956 KB	Output is correct
12	Correct	2 ms	4956 KB	Output is correct
13	Execution timed out	1562 ms	5212 KB	Time limit exceeded
14	Halted	0 ms	0 KB	-

Subtask #2

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	4956 KB	Output is correct
2	Correct	3 ms	4956 KB	Output is correct
3	Correct	3 ms	4956 KB	Output is correct
4	Correct	3 ms	4956 KB	Output is correct
5	Correct	3 ms	4956 KB	Output is correct
6	Correct	3 ms	4956 KB	Output is correct
7	Correct	2 ms	4956 KB	Output is correct
8	Correct	4 ms	4956 KB	Output is correct
9	Correct	3 ms	5000 KB	Output is correct
10	Correct	3 ms	4956 KB	Output is correct
11	Correct	2 ms	4956 KB	Output is correct
12	Correct	2 ms	4956 KB	Output is correct
13	Execution timed out	1562 ms	5212 KB	Time limit exceeded
14	Halted	0 ms	0 KB	-

Subtask #3

0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	4956 KB	Output is correct
2	Correct	3 ms	4956 KB	Output is correct
3	Correct	3 ms	4956 KB	Output is correct
4	Correct	3 ms	4956 KB	Output is correct
5	Correct	3 ms	4956 KB	Output is correct
6	Correct	3 ms	4956 KB	Output is correct
7	Correct	2 ms	4956 KB	Output is correct
8	Correct	4 ms	4956 KB	Output is correct
9	Correct	3 ms	5000 KB	Output is correct
10	Correct	3 ms	4956 KB	Output is correct
11	Correct	2 ms	4956 KB	Output is correct
12	Correct	2 ms	4956 KB	Output is correct
13	Execution timed out	1562 ms	5212 KB	Time limit exceeded
14	Halted	0 ms	0 KB	-

Subtask #4

0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	4956 KB	Output is correct
2	Correct	3 ms	4956 KB	Output is correct
3	Correct	3 ms	4956 KB	Output is correct
4	Correct	3 ms	4956 KB	Output is correct
5	Correct	3 ms	4956 KB	Output is correct
6	Correct	3 ms	4956 KB	Output is correct
7	Correct	2 ms	4956 KB	Output is correct
8	Correct	4 ms	4956 KB	Output is correct
9	Correct	3 ms	5000 KB	Output is correct
10	Correct	3 ms	4956 KB	Output is correct
11	Correct	2 ms	4956 KB	Output is correct
12	Correct	2 ms	4956 KB	Output is correct
13	Execution timed out	1562 ms	5212 KB	Time limit exceeded
14	Halted	0 ms	0 KB	-

Subtask #5

0 / 37.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	4956 KB	Output is correct
2	Correct	3 ms	4956 KB	Output is correct
3	Correct	3 ms	4956 KB	Output is correct
4	Correct	3 ms	4956 KB	Output is correct
5	Correct	3 ms	4956 KB	Output is correct
6	Correct	3 ms	4956 KB	Output is correct
7	Correct	2 ms	4956 KB	Output is correct
8	Correct	4 ms	4956 KB	Output is correct
9	Correct	3 ms	5000 KB	Output is correct
10	Correct	3 ms	4956 KB	Output is correct
11	Correct	2 ms	4956 KB	Output is correct
12	Correct	2 ms	4956 KB	Output is correct
13	Execution timed out	1562 ms	5212 KB	Time limit exceeded
14	Halted	0 ms	0 KB	-