This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2e5 + 500;
const int MAX_K = 1e2 + 500;
bitset<2> vis[MAX_N][MAX_K];
bitset<2> dp[MAX_N][MAX_K];
bitset<2> calc[MAX_N][MAX_K];
vector<int> white, c, B;
bitset<MAX_N> W;
string s;
int n, K;
int range_sum(int lo, int hi) {
return white[hi] - (lo - 1 >= 0 ? white[lo - 1] : 0);
}
int solve(int p, int k, bool can) {
if (p >= n) return dp[p][k][can] = (k == K);
if (calc[p][k][can]) return dp[p][k][can];
calc[p][k][can] = true;
int res = 0;
if (s[p] == '_' || s[p] == '.') {
res = max(res, solve(p + 1, k, true));
}
if (k < K && p + c[k] <= n && can && (s[p] == 'X' || s[p] == '.')) {
const int cur = range_sum(p, p + c[k] - 1);
if (cur == 0) {
res = max(res, solve(p + c[k], k + 1, false));
}
}
return dp[p][k][can] = res;
}
void backtrack(int p, int k, int can) {
if (p >= n) {
return;
}
if (vis[p][k][can]) {
return;
}
vis[p][k][can] = 1;
int white_works = 0;
if (s[p] == '_' || s[p] == '.') {
white_works = solve(p + 1, k, true);
}
int black_works = 0;
if (k < K && can && (s[p] == 'X' || s[p] == '.')) {
const int t = c[k];
if (p + t <= n) {
const int cur = range_sum(p, p + t - 1);
if (cur == 0) {
black_works = solve(p + t, k + 1, false);
}
if (black_works) {
++B[p];
--B[min(n, p + t)];
backtrack(p + t, k + 1, false);
}
}
}
if (white_works) {
W[p] = 1;
backtrack(p + 1, k, true);
}
}
string solve_puzzle(string s, vector<int> c) {
::c = c;
::s = s;
n = s.size();
K = c.size();
white = vector<int>(n);
white[0] = (s[0] == '_');
for (int i = 1; i < n; i++) {
white[i] = white[i - 1] + (s[i] == '_');
}
B = vector<int>(n + 5);
backtrack(0, 0, true);
string res = string(n, 'z');
int cur = 0;
for (int i = 0; i < n; i++) {
cur += B[i];
if (cur > 0 && W[i] > 0) {
res[i] = '?';
continue;
}
if (cur > 0) {
res[i] = 'X';
continue;
}
if (W[i] > 0) {
res[i] = '_';
continue;
}
}
return res;
}
Compilation message (stderr)
/tmp/ccexXczI.o: In function `main':
grader.cpp:(.text.startup+0x82): relocation truncated to fit: R_X86_64_32S against symbol `buf' defined in .bss section in /tmp/ccexXczI.o
grader.cpp:(.text.startup+0xa2): relocation truncated to fit: R_X86_64_PC32 against symbol `buf' defined in .bss section in /tmp/ccexXczI.o
/usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(vterminate.o): In function `__gnu_cxx::__verbose_terminate_handler()':
(.text._ZN9__gnu_cxx27__verbose_terminate_handlerEv+0x1a): relocation truncated to fit: R_X86_64_PC32 against `.bss._ZZN9__gnu_cxx27__verbose_terminate_handlerEvE11terminating'
/usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(vterminate.o): In function `__gnu_cxx::__verbose_terminate_handler()':
(.text._ZN9__gnu_cxx27__verbose_terminate_handlerEv+0x27): relocation truncated to fit: R_X86_64_PC32 against `.bss._ZZN9__gnu_cxx27__verbose_terminate_handlerEvE11terminating'
/usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(ios_init.o): In function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0x19): relocation truncated to fit: R_X86_64_32S against symbol `std::ios_base::Init::_S_refcount' defined in .bss._ZNSt8ios_base4Init11_S_refcountE section in /usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(ios.o)
/usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(ios_init.o): In function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0x59): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(globals_io.o)
/usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(ios_init.o): In function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0x60): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(globals_io.o)
/usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(ios_init.o): In function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0x6b): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(globals_io.o)
/usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(ios_init.o): In function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0x80): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(globals_io.o)
/usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(ios_init.o): In function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0x8b): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(globals_io.o)
/usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(ios_init.o): In function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0xa0): additional relocation overflows omitted from the output
collect2: error: ld returned 1 exit status
