#pragma once
#include <bits/stdc++.h>
using namespace std;
#define forr(i, x , y) for(int i = x ; i<=y;i++)
#define fore(i , x) for(int i = 0 ; i<x;i++)
auto compute_dp(int n , int K , string s , vector<int> c)
{
vector<vector<int>> dp(n + 1 , vector<int>(K + 1 , 0));
vector<vector<int>> pref(2 , vector<int>(n + 1 ,0));
forr(i , 1, n)
{
if(s[i - 1] == 'X')
pref[1][i]++;
if(s[i - 1] == '_')
pref[0][i]++;
fore(j , 2)
{
pref[j][i] += pref[j][i - 1];
}
}
forr(i , 0 , n)
{
if(pref[1][i] == 0)
dp[i][0] = 1;
}
forr(i , 1 , n)
{
forr(j , 1 , K) {
int w = dp[i - 1][j];
int b = 0;
int l = i - c[j - 1] + 1;
int r = i;
if(l >= 1)
{
if(pref[0][r] - pref[0][l - 1] == 0)
{
if(i != c[j - 1])
{
if(s[i - c[j - 1]] != 'X')
{
b = dp[i - c[j - 1] - 1][j - 1];
}
}
else
b = dp[i - c[j - 1]][j - 1];
}
}
if(s[i - 1] == '_')
dp[i][j] = w;
else if(s[i - 1] == 'X')
{
dp[i][j] = b;
}
else
{
dp[i][j] = w;
dp[i][j]|=b;
}
}
}
return dp;
}
std::string solve_puzzle(std::string s, std::vector<int> c)
{
int n = (int)s.size();
int K = (int)c.size();
for(auto &C: s)
if(C == '.')C='?';
auto dpL = compute_dp(n , K, s , c);
reverse(s.begin() , s.end());
reverse(c.begin() , c.end());
auto dpR = compute_dp(n , K , s ,c);
reverse(dpR.begin() + 1 , dpR.end());
dpR.push_back(dpR[0]);
reverse(s.begin() , s.end());
reverse(c.begin() , c.end());
vector<int> can_black(n +2 , 0);
vector<vector<int>> pref(2 ,vector<int>(n + 1 , 0));
forr(i , 1 , n)
{
pref[0][i] = pref[0][i - 1] + (s[i - 1] == '_');
pref[1][i] = pref[1][i - 1] + (s[i - 1] == 'X');
}
vector<int> val(n , 0);
forr(i , 1 , n)
{
if(s[i - 1] == '?')
{
int cur = 0;
forr(k , 0 , K)
{
cur|=(dpL[i - 1][k] && dpR[i + 1][K - k]);
}
if(cur == 1)
val[i-1]|=1;
}
}
forr(i , 1 , n)
{
if(s[i - 1] == '?' || s[i - 1] == 'X')
{
forr(k , 1 , K)
{
int lt = i , rt = c[k - 1] + i - 1;
if(rt > n)
continue;
bool checkL = ((i == 1) || s[i - 2] != 'X');
bool checkR = ((rt == n) || s[rt] != 'X');
int dpLeft ;
if(i <= 2)
dpLeft = (i <= 2 && k == 1);
else
dpLeft = dpL[i - 2][k - 1];
int dpRight;
if(rt + 2 > n)
dpRight= (rt + 2 > n && K == k);
else
dpRight = dpR[rt + 2][K - k];
if(checkL && checkR && dpLeft && dpRight && ((pref[0][rt] - pref[0][i - 1]) == 0))
{
can_black[lt]++;
can_black[min(n + 1, rt + 1)]--;
}
}
}
}
forr(i , 1 , n)
{
can_black[i]+=can_black[i - 1];
if(can_black[i])
val[i - 1]|=2;
}
fore(i , n)
{
if(val[i] == 1)
s[i] = '_';
else if(val[i] == 2)
s[i] = 'X';
else
s[i] = '?';
}
return s;
}
Compilation message
paint.cpp:1:9: warning: #pragma once in main file
1 | #pragma once
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
n = 13, m = 1 |
2 |
Correct |
0 ms |
348 KB |
n = 18, m = 1 |
3 |
Correct |
0 ms |
348 KB |
n = 17, m = 1 |
4 |
Correct |
1 ms |
348 KB |
n = 1, m = 1 |
5 |
Correct |
0 ms |
348 KB |
n = 20, m = 1 |
6 |
Correct |
1 ms |
500 KB |
n = 20, m = 1 |
7 |
Correct |
0 ms |
348 KB |
n = 20, m = 1 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
n = 13, m = 1 |
2 |
Correct |
0 ms |
348 KB |
n = 18, m = 1 |
3 |
Correct |
0 ms |
348 KB |
n = 17, m = 1 |
4 |
Correct |
1 ms |
348 KB |
n = 1, m = 1 |
5 |
Correct |
0 ms |
348 KB |
n = 20, m = 1 |
6 |
Correct |
1 ms |
500 KB |
n = 20, m = 1 |
7 |
Correct |
0 ms |
348 KB |
n = 20, m = 1 |
8 |
Correct |
0 ms |
344 KB |
n = 20, m = 5 |
9 |
Correct |
0 ms |
348 KB |
n = 18, m = 3 |
10 |
Correct |
0 ms |
348 KB |
n = 17, m = 2 |
11 |
Correct |
0 ms |
432 KB |
n = 20, m = 2 |
12 |
Correct |
1 ms |
344 KB |
n = 17, m = 4 |
13 |
Correct |
0 ms |
348 KB |
n = 17, m = 6 |
14 |
Correct |
0 ms |
348 KB |
n = 17, m = 1 |
15 |
Correct |
0 ms |
348 KB |
n = 17, m = 4 |
16 |
Correct |
0 ms |
348 KB |
n = 13, m = 3 |
17 |
Correct |
0 ms |
348 KB |
n = 18, m = 4 |
18 |
Correct |
0 ms |
348 KB |
n = 20, m = 10 |
19 |
Correct |
1 ms |
344 KB |
n = 19, m = 10 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
n = 13, m = 1 |
2 |
Correct |
0 ms |
348 KB |
n = 18, m = 1 |
3 |
Correct |
0 ms |
348 KB |
n = 17, m = 1 |
4 |
Correct |
1 ms |
348 KB |
n = 1, m = 1 |
5 |
Correct |
0 ms |
348 KB |
n = 20, m = 1 |
6 |
Correct |
1 ms |
500 KB |
n = 20, m = 1 |
7 |
Correct |
0 ms |
348 KB |
n = 20, m = 1 |
8 |
Correct |
0 ms |
344 KB |
n = 20, m = 5 |
9 |
Correct |
0 ms |
348 KB |
n = 18, m = 3 |
10 |
Correct |
0 ms |
348 KB |
n = 17, m = 2 |
11 |
Correct |
0 ms |
432 KB |
n = 20, m = 2 |
12 |
Correct |
1 ms |
344 KB |
n = 17, m = 4 |
13 |
Correct |
0 ms |
348 KB |
n = 17, m = 6 |
14 |
Correct |
0 ms |
348 KB |
n = 17, m = 1 |
15 |
Correct |
0 ms |
348 KB |
n = 17, m = 4 |
16 |
Correct |
0 ms |
348 KB |
n = 13, m = 3 |
17 |
Correct |
0 ms |
348 KB |
n = 18, m = 4 |
18 |
Correct |
0 ms |
348 KB |
n = 20, m = 10 |
19 |
Correct |
1 ms |
344 KB |
n = 19, m = 10 |
20 |
Correct |
0 ms |
348 KB |
n = 100, m = 5 |
21 |
Correct |
1 ms |
348 KB |
n = 90, m = 3 |
22 |
Correct |
0 ms |
348 KB |
n = 86, m = 2 |
23 |
Correct |
0 ms |
348 KB |
n = 81, m = 4 |
24 |
Correct |
1 ms |
512 KB |
n = 89, m = 10 |
25 |
Correct |
0 ms |
348 KB |
n = 81, m = 23 |
26 |
Correct |
0 ms |
348 KB |
n = 86, m = 8 |
27 |
Correct |
1 ms |
348 KB |
n = 53, m = 22 |
28 |
Correct |
1 ms |
356 KB |
n = 89, m = 35 |
29 |
Correct |
1 ms |
352 KB |
n = 63, m = 25 |
30 |
Correct |
1 ms |
352 KB |
n = 100, m = 50 |
31 |
Correct |
1 ms |
348 KB |
n = 99, m = 50 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
n = 13, m = 1 |
2 |
Correct |
0 ms |
348 KB |
n = 18, m = 1 |
3 |
Correct |
0 ms |
348 KB |
n = 17, m = 1 |
4 |
Correct |
1 ms |
348 KB |
n = 1, m = 1 |
5 |
Correct |
0 ms |
348 KB |
n = 20, m = 1 |
6 |
Correct |
1 ms |
500 KB |
n = 20, m = 1 |
7 |
Correct |
0 ms |
348 KB |
n = 20, m = 1 |
8 |
Correct |
0 ms |
344 KB |
n = 20, m = 5 |
9 |
Correct |
0 ms |
348 KB |
n = 18, m = 3 |
10 |
Correct |
0 ms |
348 KB |
n = 17, m = 2 |
11 |
Correct |
0 ms |
432 KB |
n = 20, m = 2 |
12 |
Correct |
1 ms |
344 KB |
n = 17, m = 4 |
13 |
Correct |
0 ms |
348 KB |
n = 17, m = 6 |
14 |
Correct |
0 ms |
348 KB |
n = 17, m = 1 |
15 |
Correct |
0 ms |
348 KB |
n = 17, m = 4 |
16 |
Correct |
0 ms |
348 KB |
n = 13, m = 3 |
17 |
Correct |
0 ms |
348 KB |
n = 18, m = 4 |
18 |
Correct |
0 ms |
348 KB |
n = 20, m = 10 |
19 |
Correct |
1 ms |
344 KB |
n = 19, m = 10 |
20 |
Correct |
0 ms |
348 KB |
n = 100, m = 5 |
21 |
Correct |
1 ms |
348 KB |
n = 90, m = 3 |
22 |
Correct |
0 ms |
348 KB |
n = 86, m = 2 |
23 |
Correct |
0 ms |
348 KB |
n = 81, m = 4 |
24 |
Correct |
1 ms |
512 KB |
n = 89, m = 10 |
25 |
Correct |
0 ms |
348 KB |
n = 81, m = 23 |
26 |
Correct |
0 ms |
348 KB |
n = 86, m = 8 |
27 |
Correct |
1 ms |
348 KB |
n = 53, m = 22 |
28 |
Correct |
1 ms |
356 KB |
n = 89, m = 35 |
29 |
Correct |
1 ms |
352 KB |
n = 63, m = 25 |
30 |
Correct |
1 ms |
352 KB |
n = 100, m = 50 |
31 |
Correct |
1 ms |
348 KB |
n = 99, m = 50 |
32 |
Incorrect |
1 ms |
344 KB |
char #4 differ - expected: '_', found: '?' |
33 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
n = 13, m = 1 |
2 |
Correct |
0 ms |
348 KB |
n = 18, m = 1 |
3 |
Correct |
0 ms |
348 KB |
n = 17, m = 1 |
4 |
Correct |
1 ms |
348 KB |
n = 1, m = 1 |
5 |
Correct |
0 ms |
348 KB |
n = 20, m = 1 |
6 |
Correct |
1 ms |
500 KB |
n = 20, m = 1 |
7 |
Correct |
0 ms |
348 KB |
n = 20, m = 1 |
8 |
Correct |
0 ms |
344 KB |
n = 20, m = 5 |
9 |
Correct |
0 ms |
348 KB |
n = 18, m = 3 |
10 |
Correct |
0 ms |
348 KB |
n = 17, m = 2 |
11 |
Correct |
0 ms |
432 KB |
n = 20, m = 2 |
12 |
Correct |
1 ms |
344 KB |
n = 17, m = 4 |
13 |
Correct |
0 ms |
348 KB |
n = 17, m = 6 |
14 |
Correct |
0 ms |
348 KB |
n = 17, m = 1 |
15 |
Correct |
0 ms |
348 KB |
n = 17, m = 4 |
16 |
Correct |
0 ms |
348 KB |
n = 13, m = 3 |
17 |
Correct |
0 ms |
348 KB |
n = 18, m = 4 |
18 |
Correct |
0 ms |
348 KB |
n = 20, m = 10 |
19 |
Correct |
1 ms |
344 KB |
n = 19, m = 10 |
20 |
Correct |
0 ms |
348 KB |
n = 100, m = 5 |
21 |
Correct |
1 ms |
348 KB |
n = 90, m = 3 |
22 |
Correct |
0 ms |
348 KB |
n = 86, m = 2 |
23 |
Correct |
0 ms |
348 KB |
n = 81, m = 4 |
24 |
Correct |
1 ms |
512 KB |
n = 89, m = 10 |
25 |
Correct |
0 ms |
348 KB |
n = 81, m = 23 |
26 |
Correct |
0 ms |
348 KB |
n = 86, m = 8 |
27 |
Correct |
1 ms |
348 KB |
n = 53, m = 22 |
28 |
Correct |
1 ms |
356 KB |
n = 89, m = 35 |
29 |
Correct |
1 ms |
352 KB |
n = 63, m = 25 |
30 |
Correct |
1 ms |
352 KB |
n = 100, m = 50 |
31 |
Correct |
1 ms |
348 KB |
n = 99, m = 50 |
32 |
Incorrect |
1 ms |
344 KB |
char #4 differ - expected: '_', found: '?' |
33 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
n = 13, m = 1 |
2 |
Correct |
0 ms |
348 KB |
n = 18, m = 1 |
3 |
Correct |
0 ms |
348 KB |
n = 17, m = 1 |
4 |
Correct |
1 ms |
348 KB |
n = 1, m = 1 |
5 |
Correct |
0 ms |
348 KB |
n = 20, m = 1 |
6 |
Correct |
1 ms |
500 KB |
n = 20, m = 1 |
7 |
Correct |
0 ms |
348 KB |
n = 20, m = 1 |
8 |
Correct |
0 ms |
344 KB |
n = 20, m = 5 |
9 |
Correct |
0 ms |
348 KB |
n = 18, m = 3 |
10 |
Correct |
0 ms |
348 KB |
n = 17, m = 2 |
11 |
Correct |
0 ms |
432 KB |
n = 20, m = 2 |
12 |
Correct |
1 ms |
344 KB |
n = 17, m = 4 |
13 |
Correct |
0 ms |
348 KB |
n = 17, m = 6 |
14 |
Correct |
0 ms |
348 KB |
n = 17, m = 1 |
15 |
Correct |
0 ms |
348 KB |
n = 17, m = 4 |
16 |
Correct |
0 ms |
348 KB |
n = 13, m = 3 |
17 |
Correct |
0 ms |
348 KB |
n = 18, m = 4 |
18 |
Correct |
0 ms |
348 KB |
n = 20, m = 10 |
19 |
Correct |
1 ms |
344 KB |
n = 19, m = 10 |
20 |
Correct |
0 ms |
348 KB |
n = 100, m = 5 |
21 |
Correct |
1 ms |
348 KB |
n = 90, m = 3 |
22 |
Correct |
0 ms |
348 KB |
n = 86, m = 2 |
23 |
Correct |
0 ms |
348 KB |
n = 81, m = 4 |
24 |
Correct |
1 ms |
512 KB |
n = 89, m = 10 |
25 |
Correct |
0 ms |
348 KB |
n = 81, m = 23 |
26 |
Correct |
0 ms |
348 KB |
n = 86, m = 8 |
27 |
Correct |
1 ms |
348 KB |
n = 53, m = 22 |
28 |
Correct |
1 ms |
356 KB |
n = 89, m = 35 |
29 |
Correct |
1 ms |
352 KB |
n = 63, m = 25 |
30 |
Correct |
1 ms |
352 KB |
n = 100, m = 50 |
31 |
Correct |
1 ms |
348 KB |
n = 99, m = 50 |
32 |
Incorrect |
1 ms |
344 KB |
char #4 differ - expected: '_', found: '?' |
33 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
n = 13, m = 1 |
2 |
Correct |
0 ms |
348 KB |
n = 18, m = 1 |
3 |
Correct |
0 ms |
348 KB |
n = 17, m = 1 |
4 |
Correct |
1 ms |
348 KB |
n = 1, m = 1 |
5 |
Correct |
0 ms |
348 KB |
n = 20, m = 1 |
6 |
Correct |
1 ms |
500 KB |
n = 20, m = 1 |
7 |
Correct |
0 ms |
348 KB |
n = 20, m = 1 |
8 |
Correct |
0 ms |
344 KB |
n = 20, m = 5 |
9 |
Correct |
0 ms |
348 KB |
n = 18, m = 3 |
10 |
Correct |
0 ms |
348 KB |
n = 17, m = 2 |
11 |
Correct |
0 ms |
432 KB |
n = 20, m = 2 |
12 |
Correct |
1 ms |
344 KB |
n = 17, m = 4 |
13 |
Correct |
0 ms |
348 KB |
n = 17, m = 6 |
14 |
Correct |
0 ms |
348 KB |
n = 17, m = 1 |
15 |
Correct |
0 ms |
348 KB |
n = 17, m = 4 |
16 |
Correct |
0 ms |
348 KB |
n = 13, m = 3 |
17 |
Correct |
0 ms |
348 KB |
n = 18, m = 4 |
18 |
Correct |
0 ms |
348 KB |
n = 20, m = 10 |
19 |
Correct |
1 ms |
344 KB |
n = 19, m = 10 |
20 |
Correct |
0 ms |
348 KB |
n = 100, m = 5 |
21 |
Correct |
1 ms |
348 KB |
n = 90, m = 3 |
22 |
Correct |
0 ms |
348 KB |
n = 86, m = 2 |
23 |
Correct |
0 ms |
348 KB |
n = 81, m = 4 |
24 |
Correct |
1 ms |
512 KB |
n = 89, m = 10 |
25 |
Correct |
0 ms |
348 KB |
n = 81, m = 23 |
26 |
Correct |
0 ms |
348 KB |
n = 86, m = 8 |
27 |
Correct |
1 ms |
348 KB |
n = 53, m = 22 |
28 |
Correct |
1 ms |
356 KB |
n = 89, m = 35 |
29 |
Correct |
1 ms |
352 KB |
n = 63, m = 25 |
30 |
Correct |
1 ms |
352 KB |
n = 100, m = 50 |
31 |
Correct |
1 ms |
348 KB |
n = 99, m = 50 |
32 |
Incorrect |
1 ms |
344 KB |
char #4 differ - expected: '_', found: '?' |
33 |
Halted |
0 ms |
0 KB |
- |