제출 #727447

#제출 시각아이디문제언어결과실행 시간메모리
727447Yell0Paint By Numbers (IOI16_paint)C++17
32 / 100
1 ms340 KiB
#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; 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&&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<K) { 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>=0) { 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...