#pragma region template
#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long; using vi = vector<int>;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define per(i,a,b) for (auto i = (b); i >= (a); --i)
#define all(x) begin(x), end(x)
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)
#define fi first
#define se second
#define dbg(x) cerr << #x << ": " << (x) << endl;
#pragma endregion template
// 관찰 1-1. 어떤 ?의 인덱스 i에 대해, 문자를 X로 대체 불가능 <-> 문자가 _로 고정
// 관찰 1-2. 어떤 ?의 인덱스 i에 대해, 문자를 _로 대체 불가능 <-> 문자가 X로 고정
// 관찰 1-3. 어떤 ?의 인덱스 i에 대해, 그런거 없으면 그냥 ?
// 생각 1. "....."꼴은 편하게 풀 수 있다
// 생각 2. X 또는 _가 개입하는 순간 불편한 사항이 많아진다
// 생각 3. 불편한 것들에 집중하여 고민해보자
// 생각 4. 결국 full 솔루션은 nk+nlog 같은거? 정도 허용할 것 같다
// 생각 5. 파라매트릭 서치가 유용한 상황이 발생할 수 있을 것 같으니 지속적으로 의식하자
// 보조풀이 1. 어떤 ?의 인덱스 i에 대해, 문자가 X로 고정될 조건은,
// - 즉 문자를 _로 대체 불가능함은,
// - p(i) := 1..i를 앞쪽 블록들로 valid하게 구성할 때, 사용할 수 있는 블록의 최댓값
// - s(i) := i..n를 뒷쪽 블록들로 valid하게 구성할 때, 사용할 수 있는 블록의 최댓값
// - 전처리에는 O(nk) 정도 소요될 것 같다
// - ..일때, p(i-1)+s(i+1) < k라는 것과 동치이다
// 보조풀이 2. 어떤 ?의 인덱스 i에 대해, 문자가 _로 고정될 조건은,
// - 즉 문자를 X로 대체 불가능함은,
// - 모든 x=1..k에 대해
// - i를 포함하는 모든 길이가 c[x]인 구간 [s,e]에 대해서
// - S[s-1] != 'X' && S[e+1] != 'X'이며,
// - S[s],..,S[e] != '_' 이며,
// - p(s-2) >= x-1 && s(e+2) >= k-x
// - ..라는 조건이 하나도 만족하지 않음
// - 을 만족함을 의미한다
// - 모든 구간을 둘러보는 것은 오래 걸린다
// - sum c의 bound가 n이므로 인덱스당 n만큼 걸린다
// - 그래도 나름 이 정도면 90점이 나오겠으니 해보자!
const int N = 5005, K = 105;
int n, k;
int cX[N], c_[N];
char S[N];
int c[N];
bool can_set_all_X(int l, int r) {
if (1 <= l && l <= r && r <= n)
return c_[r] - c_[l-1] == 0;
else return false;
}
int p(int i) {
static bool ready[N]{};
static int dp[N]{};
if (i == -1) return 0;
if (i == 0) return 0;
if (ready[i]) return dp[i];
ready[i] = true;
dp[i] = p(i-1);
if (dp[i] == k) return dp[i];
// challenge for dp[i]+1
int x = dp[i]+1; // c[x]
if (i-c[x] < 0) return dp[i];
if (S[ i-c[x] ] == 'X') return dp[i];
if (!can_set_all_X(i-c[x]+1, i)) return dp[i];
if (i-c[x] == 0) {
if (dp[i] == 0) return ++dp[i];
return dp[i];
}
assert(i-c[x] > 0);
if (p(i-c[x]-1) == dp[i]) {
return ++dp[i];
}
return dp[i];
}
int s(int i) {
static bool ready[N]{};
static int dp[N]{};
if (i == n+2) return 0;
if (i == n+1) return 0;
if (ready[i]) return dp[i];
ready[i] = true;
dp[i] = s(i+1);
if (dp[i] == k) return dp[i];
// challenge for dp[i]+1
int x = k-dp[i];
if (i+c[x] > n+1) return dp[i];
if (S[ i+c[x] ] == 'X') return dp[i];
if (!can_set_all_X(i, i+c[x]-1)) return dp[i];
if (i+c[x] == n+1) {
if (dp[i] == 0) return ++dp[i];
return dp[i];
}
assert(i+c[x] < n+1);
if (s(i+c[x]+1) == dp[i]) {
return ++dp[i];
}
return dp[i];
}
void precalc(const string &s, const vi &c) {
n = siz(s), k = siz(c);
rep(i,1,n) S[i] = s[i-1];
rep(i,1,k) ::c[i] = c[i-1];
rep(i,1,n+2) cX[i] = cX[i-1]+(S[i]=='X');
rep(i,1,n+2) c_[i] = c_[i-1]+(S[i]=='_');
}
bool fixX(int i) {
assert(i-1 >= -1 && i+1 <= n+2);
return p(i-1)+s(i+1) < k;
}
bool fix_(int i) {
rep(x,1,k) {
for (int s = i-c[x]+1, e = i; s <= i && i <= e; s++, e++) {
if (s < 1) continue;
if (e > n) break;
if (S[s-1] != 'X' && S[e+1] != 'X') {
if (can_set_all_X(s,e)) {
// cerr << "[s,e]: " << s << ' ' << e << endl;
// cerr << "[x-1,k-x]: " << x-1 << ' ' << k-x << endl;
if (p(s-2) >= x-1 && ::s(e+2) >= k-x) {
return false;
}
}
}
}
}
return true;
}
string solve_puzzle(string a, vi c) {
string res(n,'$');
precalc(a,c);
rep(i,1,n) {
if (S[i] != '.') {
res[i-1] = S[i];
continue;
}
if (fixX(i)) res[i-1] = 'X';
else if (fix_(i)) res[i-1] = '_';
else res[i-1] = '?';
}
// rep(i,0,n) cerr << S[i] << ' ';
// cerr << endl;
// rep(i,0,n) cerr << p(i) << ' ';
// cerr << endl;
// rep(i,0,n) cerr << s(i) << ' ';
// cerr << '\n' << res;
return res;
}
#pragma region grader
#ifdef LOCAL
const int S_MAX_LEN = 200 * 1000;
char buf[S_MAX_LEN + 1];
int main() {
assert(1 == scanf("%s", buf));
std::string s = buf;
int c_len;
assert(1 == scanf("%d", &c_len));
std::vector<int> c(c_len);
for (int i = 0; i < c_len; i++) {
assert(1 == scanf("%d", &c[i]));
}
std::string ans = solve_puzzle(s, c);
printf("%s\n", ans.data());
return 0;
}
#endif
#pragma endregion grader
Compilation message
paint.cpp:1: warning: ignoring '#pragma region template' [-Wunknown-pragmas]
1 | #pragma region template
|
paint.cpp:13: warning: ignoring '#pragma endregion template' [-Wunknown-pragmas]
13 | #pragma endregion template
|
paint.cpp:169: warning: ignoring '#pragma region grader' [-Wunknown-pragmas]
169 | #pragma region grader
|
paint.cpp:191: warning: ignoring '#pragma endregion grader' [-Wunknown-pragmas]
191 | #pragma endregion grader
|
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Incorrect length: expected: '13', found: '14' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Incorrect length: expected: '13', found: '14' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Incorrect length: expected: '13', found: '14' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Incorrect length: expected: '13', found: '14' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Incorrect length: expected: '13', found: '14' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Incorrect length: expected: '13', found: '14' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Incorrect length: expected: '13', found: '14' |
| 2 |
Halted |
0 ms |
0 KB |
- |
