이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define INF 10000000000000000
#define MOD 1000000017
#define mid(l, u) ((l+u)/2)
#define rchild(i) (i*2 + 2)
#define lchild(i) (i*2 + 1)
using namespace std;
const int N = 200005;
const int K = 105;
int n, k, temp;
vector<int> cc;
string str;
int sum[N], dp[N][K], black[N];
bool white[N];
int f(int i, int j){
if(i>n) return (j>=k);
if(dp[i][j]!=-1) return dp[i][j];
if(j>=k){
if(str[i]=='X') return dp[i][j] = 0;
if(f(i+1, j)==1){
white[i-1] = true;
return dp[i][j] = 1;
}
return dp[i][j] = 0;
}
if(str[i-1]=='_'){
if(f(i+1, j)>=1){
white[i-1] = true;
return dp[i][j] = 1;
}
return dp[i][j] = 0;
}
if((i+cc[j]-1)>n){
return dp[i][j] = 0;
}
int ans = 0;
int whiteinrange = (sum[i+cc[j]-1] - sum[i-1]);
if((whiteinrange==0) && (((i+cc[j]-1)>=n)||(str[i+cc[j]-1]!='X'))) {
int temp = f(i+cc[j]+1, j+1);
if(temp>=1){
black[i-1]++;
black[i+cc[j]-1]--;
white[i+cc[j]-1] = true;
}
ans+=temp;
}
if(str[i-1]!='X'){
int temp = f(i+1, j);
if(temp>=1){
white[i-1] = true;
}
ans+=temp;
}
if(ans>=1) ans = 1;
return dp[i][j] = ans;
}
string solve_puzzle(string s, vector<int> c){
str = s;
cc = c;
k = c.size();
n = s.length();
string ans = s;
sum[0] = 0;
for(int i = 0;i<n;i++) sum[i+1] = (s[i]=='_') + sum[i];
for(int i = 0;i<n;i++){
white[i] = black[i] = 0;
ans[i] = '?';
for(int j = 0;j<=k;j++){
dp[i][j] = -1;
}
}
f(1, 0);
for(int i = 1;i<n;i++) black[i]+=black[i-1];
for(int i = 0;i<n;i++){
if(black[i]==0) ans[i] = '_';
if(white[i]==false) ans[i] = 'X';
}
return ans;
}
/*int main(){
string s;
int kk;
vector<int> c;
cin>>s>>kk;
for(int i = 0;i<kk;i++){
int temp;
cin>>temp;
c.push_back(temp);
}
cout<<solve_puzzle(s, c)<<endl;
}*/
컴파일 시 표준 에러 (stderr) 메시지
paint.cpp: In function 'std::__cxx11::string solve_puzzle(std::__cxx11::string, std::vector<int>)':
paint.cpp:66:29: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
white[i] = black[i] = 0;
~~~~~~~~~^~~
# | 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... |