이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "paint.h"
#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,i,e,f,g,n,m,k,l,pdp[200005][102],sdp[200005][102],A[200005],B[200005],C[200005];
string s1;
std::string solve_puzzle(std::string s, std::vector<int> c) {
n=s.size(); m=c.size();
c.insert(c.begin(),0);
s='*'+s+'*';
for(long long i=1;i<=n;i++) {
A[i]=A[i-1];
if(s[i]=='_') A[i]++;
}
for(long long i=0;i<=n+1;i++) {
if(s[i]=='X') break;
pdp[i][0]=1;
}
for(long long i=n+1;i>=0;i--) {
if(s[i]=='X') break;
sdp[i][m+1]=1;
}
for(long long i=1;i<=n;i++) {
for(long long j=1;j<=m;j++) {
if(s[i]!='X') pdp[i][j]=pdp[i-1][j];
if(pdp[i][j]==1) continue;
if(s[i]!='_' && i-c[j]+1>=1 && A[i]-A[i-c[j]]==0) {
if(i-c[j]+1==1) { if(j==1)pdp[i][j]=1; }
else if(s[i-c[j]]!='X') pdp[i][j]=pdp[i-c[j]-1][j-1];
}
}
}
for(long long i=n;i>=1;i--) {
for(long long j=m;j>=1;j--) {
if(s[i]!='X') sdp[i][j]=sdp[i+1][j];
if(sdp[i][j]==1) continue;
if(s[i]!='_' && i+c[j]-1<=n && A[i+c[j]-1]-A[i-1]==0) {
if(i+c[j]-1==n) { if(j==m) sdp[i][j]=1; }
else if(s[i+c[j]]!='X') sdp[i+c[j]+1][j+1];
}
}
}
for(long long i=1;i<=n;i++) {
if(s[i]=='X') continue;
for(long long j=0;j<=m;j++) {
if(pdp[i-1][j]==1 && sdp[i+1][j+1]==1) B[i]=1;
}
}
for(long long i=1;i<=n;i++) {
if(s[i]=='_') continue;
for(long long j=1;j<=m;j++) {
if(i-c[j]+1<=0) continue;
if(i-c[j]+1>1 && s[i-c[j]]=='X') continue;
a=0; b=0;
if(i-c[j]-1<0) { if(j==1) a=1; }
else if(s[i-c[j]]!='X') a=pdp[i-c[j]-1][j-1];
if(i+2>n+1) { if(j==m) b=1; }
else if(s[i+1]!='X') b=sdp[i+2][j+1];
if(a==1 && b==1 && A[i]-A[i-c[j]]==0) { C[i+1]--; C[i-c[j]+1]++; }
}
}
for(long long i=1;i<=n;i++) {
C[i]+=C[i-1];
}
for(long long i=1;i<=n;i++) {
if(B[i]==1 && C[i]!=0) s1+='?';
else if(B[i]==1) s1+='_';
else if(C[i]!=0) s1+='X';
}
return s1;
}/*
int main() {
cout<<solve_puzzle(".", {1});
}*/
# | 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... |