Submission #311113

#	Time	Username	Problem	Language	Result	Execution time	Memory
311113		juggernaut	Paint By Numbers (IOI16_paint)	C++14	80 / 100	10 ms	896 KiB

paint

#include"paint.h"
#include<bits/stdc++.h>
//#include"grader.cpp"
using namespace std;
string s;
vector<int>c;
int n,m;
bool dp[105][105],flag[105][105];
bool app(){
    for(int i=1;i<=n;i++){
            flag[i][i]=(s[i-1]=='_');
            for(int j=i+1;j<=n;j++)
                flag[i][j]=(flag[i][j-1]||s[j-1]=='_');
    }
    dp[0][0]=1;
    for(int i=0;i<=m;i++)
        for(int j=1;j<=n;j++){
            dp[i][j]=0;
            if(s[j-1]!='X')dp[i][j]|=dp[i][j-1];
            if(i){
                if(j>c[i-1])
                    dp[i][j]|=!flag[j-c[i-1]+1][j]&&s[j-1-c[i-1]]!='X'&&dp[i-1][j-c[i-1]-1];
                if(j==c[i-1])
                    dp[i][j]|=!flag[1][j]&&i==1;
            }
        }
    return dp[m][n];
}
string solve_puzzle(string S,vector<int>C){
    n=S.size();
    m=C.size();
    s=S;
    c.resize(m);
    copy(C.begin(),C.end(),c.begin());
    string res=s;
    for(int i=0;i<n;i++)
        if(s[i]=='.'){
            s[i]='X';
            bool black=app();
            s[i]='_';
            bool white=app();
            s[i]='.';
            if(white&&black)res[i]='?';
            else if(black)res[i]='X';
            else if(white)res[i]='_';
        }
    return res;
}

• Subtask 1: 7 / 7
• Subtask 2: 3 / 3
• Subtask 3: 22 / 22
• Subtask 4: 27 / 27
• Subtask 5: 21 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10