이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "paint.h"
#include<bits/stdc++.h>
#include <cstdlib>
#define ll int
#define pb push_back
#define mp make_pair
#define ld long double
#define F first
#define S second
#define pii pair<ll,ll>
using namespace :: std;
const ll maxn=2e5+10;
const ll inf=1e9+900;
const ll maxk=100;
bool dp[maxn][maxk];
bool dpf[maxn][maxk];
string gs;
bool safnadasht(ll l,ll r){
if(l<0 || gs.size()<=r)return 0;
for(ll i=l;i<=r;i++)if(gs[i]=='_')return 0;
return 1;
}
void make_dp(string s,vector<ll> c){
gs=s;
ll n=s.size();
ll k=c.size();
memset(dp,0,sizeof dp);
memset(dpf,0,sizeof dpf);
dp[0][0]=1;
dpf[0][0]=1;
for(ll i=1;i<=n;i++){
for(ll j=0;j<=k;j++){
if(s[i-1]=='_'){
dp[i][j]=0;
dpf[i][j]=dpf[i-1][j]|dp[i-1][j];
}
else{
if(j && safnadasht(i-c[j-1],i-1)){
dp[i][j]=dpf[i-c[j-1]][j-1];
}
if(s[i-1]=='.'){
dpf[i][j]|=dpf[i-1][j]|dp[i-1][j];
}
}
}
}
}
bool valid(string s,vector<int> c){
make_dp(s,c);
ll n=s.size();
ll k=c.size();
return (dpf[n][k] || dp[n][k]);
}
string slowSolve(string s,vector<int> c){
ll n=s.size();
ll k=c.size();
string ans=s;
for(ll i=0;i<n;i++){
if(s[i]=='.'){
s[i]='_';
bool q=valid(s,c);
s[i]='X';
bool w=valid(s,c);
if(q && !w){
ans[i]='_';
}
if(!q && w){
ans[i]='X';
}
if(w && q){
ans[i]='?';
}
s[i]='.';
}
}
return ans;
}
bool sdp[maxn][maxk];
bool sdpf[maxn][maxk];
ll prr[maxn];
string solve_puzzle(string s, vector<int> c) {
make_dp(s,c);
ll n=s.size();
ll k=c.size();
for(ll i=0;i<=n;i++){
for(ll j=0;j<=k;j++){
sdp[i][j]=dp[i][j];
sdpf[i][j]=dpf[i][j];
}
}
reverse(s.begin(),s.end());
reverse(c.begin(),c.end());
make_dp(s,c);
reverse(s.begin(),s.end());
reverse(c.begin(),c.end());
for(ll j=0;j<k;j++){
vector<ll> star;
for(ll i=0;i<n;i++){
if(sdp[i+1][j+1] && n-1-i+c[j]>=0 && dp[n-1-i+c[j]][k-j]){
star.pb(i);
}
}
for(auto v:star){
prr[v+1]--;
prr[v-c[j]+1]++;
}
}
for(ll i=1;i<n;i++)prr[i]+=prr[i-1];
string ans=s;
for(ll i=0;i<n;i++){
if(s[i]=='.'){
if(prr[i]==0){
ans[i]='_';
continue;
}
bool mish=0;
for(ll j=0;j<=k;j++){
if(sdpf[i+1][j] && dpf[n-i][k-j]){
mish=1;
}
}
if(mish){
ans[i]='?';
}else{
ans[i]='X';
}
}
}
return ans;
}
컴파일 시 표준 에러 (stderr) 메시지
paint.cpp: In function 'bool safnadasht(int, int)':
paint.cpp:24:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(l<0 || gs.size()<=r)return 0;
~~~~~~~~~^~~
paint.cpp: In function 'std::__cxx11::string slowSolve(std::__cxx11::string, std::vector<int>)':
paint.cpp:63:8: warning: unused variable 'k' [-Wunused-variable]
ll k=c.size();
^
# | 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... |