#include <bits/stdc++.h>
using namespace std;
char s[200007];
vector<int> c;
string ans;
bool pref[200007][107],li[200007][107];
bool suff[200007][107],li2[200007][107];
bool white,black;
int sum[200007],n,k;
bool ff(int pos,int k){
if(k==-1)return true;
else if(pos<=0)return false;
if(li[pos][k])return pref[pos][k];
li[pos][k]=true;
pref[pos][k]=ff(pos-1,k);
if(pos>=c[k] and sum[pos]-sum[pos-c[k]]==0 and s[pos-c[k]]!='X' and ff(pos-c[k]-1,k-1)){
pref[pos][k]=true;
}
return pref[pos][k];
}
bool ff2(int pos,int k){
if(k==c.size())return true;
else if(pos>=n+1)return false;
if(li2[pos][k])return suff[pos][k];
li2[pos][k]=true;
suff[pos][k]=ff(pos+1,k);
if(pos+c[k]-1<=n and sum[pos+c[k]-1]-sum[pos]==0 and s[pos+c[k]]!='X' and ff2(pos+c[k]+1,k+1)){
suff[pos][k]=true;
}
return suff[pos][k];
}
string solve_puzzle(string S, vector<int> C){
c=C; n=int(S.size()); k=int(C.size());
for(int i=1;i<=n;i++){
s[i]=S[i-1]; sum[i]=sum[i-1];
if(s[i]=='_')sum[i]++;
}
for(int i=1;i<=n;i++){
if(s[i]!='.'){
ans.push_back(s[i]); continue;
}
white=black=false;
for(int f=0;f<=k;f++){
if(ff(i-1,f) and ff2(i+1,f+1))white=true;
}
for(int f=0;f<=k;f++){
for(int t=max(i-c[f]+1,1);t<=i;t++){
if(sum[t+c[f]-1]-sum[t-1]!=0 or s[t-1]=='X' or s[t+c[f]]=='X')continue;
if(ff(t-2,f-1) and ff2(t+c[f]+1,f+1))black=true;
}
}
if(white and black)ans.push_back('?');
if(!white and black)ans.push_back('X');
if(white and !black)ans.push_back('_');
}
if(ans.size()!=n)cout<<1/0;
return ans;
}
Compilation message
paint.cpp: In function 'bool ff2(int, int)':
paint.cpp:29:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | if(k==c.size())return true;
| ~^~~~~~~~~~
paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:73:18: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
73 | if(ans.size()!=n)cout<<1/0;
| ~~~~~~~~~~^~~
paint.cpp:73:29: warning: division by zero [-Wdiv-by-zero]
73 | if(ans.size()!=n)cout<<1/0;
| ~^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
340 KB |
char #0 differ - expected: '?', found: 'X' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
340 KB |
char #0 differ - expected: '?', found: 'X' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
340 KB |
char #0 differ - expected: '?', found: 'X' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
340 KB |
char #0 differ - expected: '?', found: 'X' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
340 KB |
char #0 differ - expected: '?', found: 'X' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
340 KB |
char #0 differ - expected: '?', found: 'X' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
340 KB |
char #0 differ - expected: '?', found: 'X' |
2 |
Halted |
0 ms |
0 KB |
- |