이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "paint.h"
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define inside sl<=l&&r<=sr
#define outside r<sl||sr<l
#define orta ((l+r)>>1)
#define INF 1000000009
#define mod 1000000007
#define ppair(x); cerr << "(" << x.first << ", " << x.second << ")\n";
#define bas(x) #x << ": " << x << " "
#define prarr(x, n); cerr << #x << ": "; for(int qsd = 0; qsd < n; qsd++) cerr << x[qsd] << " "; cerr << "\n";
#define prarrv(x); cerr << #x << ": "; for(int qsd = 0; qsd < (int)x.size(); qsd++) cerr << x[qsd] << " "; cerr << "\n";
using namespace std;
typedef long long ll;
string s;
int pre[200005];
string ans;
vector<int> c;
vector<int> xarr;
int dp[200005][101];
int varmi(int l, int r){
int ans = 0;
if (l == 0) ans = pre[r];
else ans = pre[r] - pre[l-1];
if (ans > 0) return 1;
else return 0;
}
void merge(int i, char c){
if (ans[i] == '!') ans[i] = c;
else if (ans[i] == '_' && c == 'X') ans[i] = '?';
else if (ans[i] == 'X' && c == '_') ans[i] = '?';
}
void update(int l, int r){
xarr[l]++;
xarr[r+1]--;
}
int f(int i, int k){
//cout << "f(" << i << ", " << k << ")" << endl;
if (i >= s.size()) return (k == c.size());
if (dp[i][k] != -1) return dp[i][k];
if (k != c.size() && i+c[k] > s.size()) return dp[i][k] = 0;
int ans = 0;
if (k < c.size() && (varmi(i, c[k]+i-1) == 0) && (c[k]+i == s.size() || s[i+c[k]] != 'X')){
ans = f(i+c[k]+1, k+1);
if (ans){
update(i, i+c[k]-1);
merge(i+c[k], '_');
}
}
int ans2 = 0;
if (s[i] != 'X') ans2 = f(i+1, k);
if (ans2) merge(i, '_');
return dp[i][k] = (ans|ans2);
}
string solve_puzzle(string S, vector<int> C) {
c = C;
s = S;
int sum = 0;
for (int i = 0; i < s.size(); i++){
if (s[i] == '_') sum++;
pre[i] = sum;
}
ans = "";
for (int i = 0; i < s.size(); i++) ans += (s[i] == '_' ? '_' : '!');
//for (int i = 0; i < s.size(); i++) if (s[i] == 'X') ans[i] = 'X';
xarr.resize(s.size()+1);
for (int i = 0; i < s.size(); i++) xarr[i] = 0;
for (int i = 0; i < s.size(); i++) for (int j = 0; j <= c.size(); j++) dp[i][j] = -1;
f(0, 0);
if (xarr[0] > 0) merge(0, 'X');
for (int i = 1; i < s.size(); i++){
xarr[i] += xarr[i-1];
if (xarr[i] > 0) merge(i, 'X');
}
return ans;
}
컴파일 시 표준 에러 (stderr) 메시지
paint.cpp: In function 'int f(int, int)':
paint.cpp:47:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (i >= s.size()) return (k == c.size());
~~^~~~~~~~~~~
paint.cpp:47:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (i >= s.size()) return (k == c.size());
~~^~~~~~~~~~~
paint.cpp:49:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (k != c.size() && i+c[k] > s.size()) return dp[i][k] = 0;
~~^~~~~~~~~~~
paint.cpp:49:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (k != c.size() && i+c[k] > s.size()) return dp[i][k] = 0;
~~~~~~~^~~~~~~~~~
paint.cpp:51:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (k < c.size() && (varmi(i, c[k]+i-1) == 0) && (c[k]+i == s.size() || s[i+c[k]] != 'X')){
~~^~~~~~~~~~
paint.cpp:51:59: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (k < c.size() && (varmi(i, c[k]+i-1) == 0) && (c[k]+i == s.size() || s[i+c[k]] != 'X')){
paint.cpp: In function 'std::__cxx11::string solve_puzzle(std::__cxx11::string, std::vector<int>)':
paint.cpp:68:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < s.size(); i++){
~~^~~~~~~~~~
paint.cpp:73:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < s.size(); i++) ans += (s[i] == '_' ? '_' : '!');
~~^~~~~~~~~~
paint.cpp:77:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < s.size(); i++) xarr[i] = 0;
~~^~~~~~~~~~
paint.cpp:79:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < s.size(); i++) for (int j = 0; j <= c.size(); j++) dp[i][j] = -1;
~~^~~~~~~~~~
paint.cpp:79:55: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < s.size(); i++) for (int j = 0; j <= c.size(); j++) dp[i][j] = -1;
~~^~~~~~~~~~~
paint.cpp:84:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 1; i < s.size(); i++){
~~^~~~~~~~~~
# | 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... |