이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/// In The Name Of God
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define pp pop_back
#define mp make_pair
#define sz(x) (int)x.size()
#define sqr(x) ((x) * 1ll * (x))
#define all(x) x.begin(), x.end()
#define Kazakhstan ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define nl '\n'
#define ioi exit(0);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int N = (int)4e5 + 7;
const int inf = (int)1e9 + 7;
const int mod = (int)1e9 + 7;
const ll linf = (ll)1e18 + 7;
const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1};
const int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
using namespace std;
int n, k;
int pref[N];
vector <int> a;
string s;
int mn_b[N], mx_b[N];
int bad[N];
bool check(int l, int r) {
return !(l ? pref[r] - pref[l - 1] : pref[r]) && (r + 1 == n || s[r + 1] != 'X');
}
int dp[N][105];
bool calc(int v, int id) {
if (v >= n) {
return id == k;
}
if (~dp[v][id]) return dp[v][id];
bool res = 0;
if (s[v] != 'X') {
res |= calc(v + 1, id);
}
if (id < k && v + a[id] <= n) {
if (check(v, v + a[id] - 1) && calc(v + a[id] + 1, id + 1)) {
mn_b[id] = max(mn_b[id], v);
mx_b[id] = min(mx_b[id], v + a[id] - 1);
res = 1;
bad[v]++;
bad[v + a[id]]--;
}
}
return dp[v][id] = res;
}
string solve_puzzle(string S, vector <int> c) {
n = sz(S);
s = S;
a = c;
k = sz(c);
// --- coppying
for (int i = 0; i < n; i++) {
pref[i] = s[i] == '_';
if (i) pref[i] += pref[i - 1];
}
for (int i = 0; i < k; i++) {
mn_b[i] = -inf;
mx_b[i] = +inf;
}
memset(dp, -1, sizeof(dp));
calc(0, 0);
for (int i = 1; i < n; i++) bad[i] += bad[i - 1];
for (int i = 0; i < k; i++) {
if (mn_b[i] <= mx_b[i] && mn_b[i] >= 0 && mx_b[i] < n) {
for (int j = mn_b[i]; j <= mx_b[i]; j++) {
s[j] = 'X';
}
}
}
for (int i = 0; i < n; i++) {
if (s[i] == '.') {
if (bad[i]) s[i] = '?';
else s[i] = '_';
}
}
return s;
}
#ifdef IOI2018
const int S_MAX_LEN = 200 * 1000;
char buf[S_MAX_LEN + 1];
int main() {
freopen ("in.txt", "r", stdin);
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
컴파일 시 표준 에러 (stderr) 메시지
paint.cpp: In function 'bool calc(int, int)':
paint.cpp:70:19: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
return dp[v][id] = res;
~~~~~~~~~~^~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |