제출 #442302

#제출 시각아이디문제언어결과실행 시간메모리
442302adamjinweiPaint By Numbers (IOI16_paint)C++14
80 / 100
2084 ms988 KiB
#include <bits/stdc++.h> #include "paint.h" #define inf 1000000007 #define mod 1000000007 //#define int long long using namespace std; template<typename T> void read(T &x) { x=0;char ch=getchar();int fh=1; while(ch<'0'||ch>'9') {if(ch=='-') fh=-1;ch=getchar();} while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); x*=fh; } template<typename T> void write(T x) { if(x<0) putchar('-'),x=-x; if(x>9) write(x/10); putchar(x%10+'0'); } template<typename T> void writeln(T x) { write(x); puts(""); } int n,m; char s[200005]; int c[105]; int sumx[200005],sumb[200005]; bool dp[200005][105]; char res[200005]; string solve_puzzle(string S,vector<int> C) { n=S.size()+1; m=C.size(); for(int i=1;i<=n;++i) { if(i!=n) s[i]=S[i-1]; else s[i]='_'; } for(int i=1;i<=m;++i) c[i]=C[i-1]; for(int i=1;i<=n;++i) if(s[i]!='.') res[i]=s[i]; else { s[i]='X'; for(int j=1;j<=n;++j) { sumx[j]=sumx[j-1]+(s[j]=='X'?1:0); sumb[j]=sumb[j-1]+(s[j]=='_'?1:0); } dp[0][0]=1; for(int j=1;j<=n;++j) for(int k=0;k<=m;++k) { dp[j][k]=0; if(dp[j-1][k]&&sumx[j]-sumx[j-1]==0) dp[j][k]=1; if(k&&j>=c[k]+1&&sumb[j-1]-sumb[j-c[k]-1]==0&&sumx[j]-sumx[j-1]==0&&dp[j-c[k]-1][k-1]) dp[j][k]=1; } bool isx=dp[n][m]; s[i]='_'; for(int j=1;j<=n;++j) { sumx[j]=sumx[j-1]+(s[j]=='X'?1:0); sumb[j]=sumb[j-1]+(s[j]=='_'?1:0); } dp[0][0]=1; for(int j=1;j<=n;++j) for(int k=0;k<=m;++k) { dp[j][k]=0; if(dp[j-1][k]&&sumx[j]-sumx[j-1]==0) dp[j][k]=1; if(k&&j>=c[k]+1&&sumb[j-1]-sumb[j-c[k]-1]==0&&sumx[j]-sumx[j-1]==0&&dp[j-c[k]-1][k-1]) dp[j][k]=1; } bool isb=dp[n][m]; if(isx&&isb) res[i]='?'; if(isx&&!isb) res[i]='X'; if(!isx&&isb) res[i]='_'; s[i]='.'; } string ans; for(int i=1;i<n;++i) ans+=res[i]; return ans; } // signed main() // { // // vector<int> vec; // // vec.push_back(3); // // // vec.push_back(4); // // solve_puzzle(".X......",vec); // return 0; // }
#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...