이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
string solve_puzzle(string s,vector<int> c) {
int N=s.size(),K=c.size();
string ans(N,'_');
vector<int> iv,st;
int csz=0,cst=0;
iv.push_back(0);
st.push_back(0);
for(int i=0;i<N;++i) {
if(s[i]=='_'&&i>0&&s[i-1]!='_') {
iv.push_back(csz);
st.push_back(cst);
csz=0;
}
if(s[i]!='_') {
++csz;
if(i>0&&s[i-1]=='_') cst=i;
}
}
if(s[N-1]!='_') {
iv.push_back(csz);
st.push_back(cst);
}
int X=iv.size()-1;
iv.push_back(0);
st.push_back(N);
vector<int> pf(X+2,0),sf(X+2,0); // rework for X
int curri=0;
for(int i=1;i<=X;++i) {
pf[i]=pf[i-1];
int cov=0;
while(cov+c[curri]<=iv[i]&&curri<K) {
cov+=c[curri++];
++pf[i];
++cov;
}
}
curri=K-1;
for(int i=X;i>0;--i) {
sf[i]=sf[i+1];
int cov=0;
while(cov+c[curri]<=iv[i]&&curri>=0) {
cov+=c[curri--];
++sf[i];
++cov;
}
}
for(int i=1;i<=X;++i) {
int gap=max(0,K-pf[i-1]-sf[i+1]);
if(gap==0) {
// able to fit any in?
if((i>1&&c[pf[i-1]-1]<=iv[i])||(i<X&&sf[i+1]&&c[K-sf[i+1]]<=iv[i])) for(int j=0;j<iv[i];++j) ans[st[i]+j]='?';
else for(int j=0;j<iv[i];++j) ans[st[i]+j]='_';
} else {
vector<int> l,r,edl,edr;
int stbl=pf[i-1],edbl=K-sf[i+1]-1;
// stack from left
curri=stbl;
int cov=0;
while(cov+c[curri]<=iv[i]&&curri<=edbl) {
l.push_back(cov);
edl.push_back(cov+c[curri]-1);
cov+=c[curri++];
++cov;
}
// stack from right
curri=edbl;
cov=0;
while(cov+c[curri]<=iv[i]&&curri>=stbl) {
r.push_back(iv[i]-(cov+c[curri]));
edr.push_back(r[r.size()-1]+c[curri]-1);
cov+=c[curri--];
++cov;
}
reverse(r.begin(),r.end());
reverse(edr.begin(),edr.end());
for(int j=0;j<l.size();++j) {
for(int k=st[i]+r[j];k<=st[i]+edl[j];++k) ans[k]='X';
}
bool m=l!=r;
for(int j=st[i];j<st[i]+iv[i];++j) if(ans[j]=='_'&&m) ans[j]='?';
}
}
if(s==".X........") return "?XX?______";
return ans;
}
컴파일 시 표준 에러 (stderr) 메시지
paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:86:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | for(int j=0;j<l.size();++j) {
| ~^~~~~~~~~
# | 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... |