Submission #799617

#	Time	Username	Problem	Language	Result	Execution time	Memory
799617		Benmath	Paint By Numbers (IOI16_paint)	C++14	100 / 100	294 ms	242332 KiB

paint

#include "paint.h"
#include<bits/stdc++.h>
using namespace std;
std::string solve_puzzle(std::string s, std::vector<int> c) {
    int n=s.size();
    int k=c.size();
    if(n==1){
        return "X";
    }
    int dp0[n][k+1];
   string ans=s;
    int dp[n][k+1];
    int dp1[n][k+1];
    int bo[n+2];
    int bijeli[n];
    int fakat_bijeli[n];
    int crni[n];
    if(s[0]!='X'){
        bijeli[0]=1;

    }else{
    bijeli[0]=0;}
    if(s[0]!='_'){
        fakat_bijeli[0]=0;
    }else{
    fakat_bijeli[0]=1;}

    int black[n];
    int white[n];
    for(int i=0;i<=n;i++){
            if(i!=n){
                black[i]=0;
                white[i]=0;
            }
        bo[i]=0;
        if(i!=0 and i<n){
            bijeli[i]=bijeli[i-1];
fakat_bijeli[i]=fakat_bijeli[i-1];
            if(s[i]!='X'){
                bijeli[i]++;
            }
if(s[i]=='_'){
    fakat_bijeli[i]++;
}
        }
    }
    for(int i=n-1;i>=0;i--){
        int y=bijeli[n-1];
        if(i!=0){
            y=y-bijeli[i-1];
        }

        if(y==(n-i)){
            dp1[i][0]=1;
        }else{
        dp1[i][0]=0;}
        for(int j=1;j<=k;j++){
            int si=c[k-j];
            dp1[i][j]=0;
            if((i+si-1)<=(n-1)){
                int x=fakat_bijeli[i+si-1];
                if(i>0){
                    x=x-fakat_bijeli[i-1];
                }
                if(x==0){
                    if((i+si-1)==(n-1)){
                        if(j==1){
                            dp1[i][j]++;
                        }
                    }else{
                    if(s[i+si]!='X'){
                            if((i+si)==(n-1)){
                                if(j==1){
                                    dp1[i][j]++;
                                }
                            }else{
                        dp1[i][j]=dp1[i+si+1][j-1];
                            }
                    }
                    }
                }
            }
            if(s[i]!='X' and i!=(n-1)){
                dp1[i][j]=max(dp1[i][j],dp1[i+1][j]);
            }
        }
    }

    for(int i=0;i<n;i++){
        if(bijeli[i]==(i+1)){
            dp[i][0]=1;
        }else{
        dp[i][0]=0;}
        dp0[i][0]=0;

        if(s[i]=='.'){
            if(i==0){
                if(dp1[i+1][k]>0){
                   white[i]++;
                }
            }else if(i<(n-1)){
                if(dp[i-1][0]>0 and dp1[i+1][k]>0){
                    white[i]++;
                }
            }else{
                if(dp[i-1][k]>0){
                    white[i]++;
                }
            }
        }

        for(int j=1;j<=k;j++){
                dp0[i][j]=0;
        dp[i][j]=0;
            int si=c[j-1];

            int t1=0;
            if((i-si+1)>=0){
                if((i-si+1)==0){

                    if(fakat_bijeli[i]==0 and j==1){
                        dp0[i][j]++;
                    }
                }else{
                    if(s[i-si]!='X'){
                        int x=fakat_bijeli[i]-fakat_bijeli[i-si];
                        if((i-si)==0){
                            if(j==1 and x==0){
                                dp0[i][j]++;
                            }
                        }else{
                        if(x==0){
                            dp0[i][j]=dp[i-si-1][j-1];
                        }
                        }
                    }
                }
            }
            dp[i][j]=dp0[i][j];
            if(s[i]!='X' and i>0){
                dp[i][j]=max(dp[i][j],dp[i-1][j]);
            }
            if(i!=0 and i!=(n-1) and s[i]=='.'){
                if(dp[i-1][j]>0 and dp1[i+1][k-j]>0){
                    white[i]++;
                }
            }
            if(i<(n-2) and s[i+1]!='X'){
                if(dp0[i][j]>0 and dp1[i+2][k-j]>0){
                    bo[i-c[j-1]+1]++;
                    bo[i+1]--;
                }
            }

        }
        if(i==(n-1)){
            if(dp0[i][k]>0){
                bo[i-c[k-1]+1]++;
                bo[i+1]--;
            }
        }else if(i==(n-2)){
        if(dp0[i][k]>0 and s[i+1]!='X'){
            bo[i-c[k-1]+1]++;
            bo[i+1]--;
        }
        }

    }

    int sum=0;
    for(int i=0;i<n;i++){
        sum=sum+bo[i];
        if(s[i]=='.'){
            if(sum>0){
                black[i]++;
            }
            if(black[i]>0 and white[i]>0){
                ans[i]='?';
            }else if(black[i]>0){
            ans[i]='X';}else{
            ans[i]='_';}
        }
    }
    return ans;
}
/*
const int S_MAX_LEN = 200 * 1000;
char buf[S_MAX_LEN + 1];

int main() {
    assert(1 == scanf("%s", buf));
    std::string s = buf;
    int c_len;
    assert(1 == scanf("%d", &c_len));
    std::vector<int> c(c_len);
    for (int i = 0; i < c_len; i++) {
        assert(1 == scanf("%d", &c[i]));
    }
    std::string ans = solve_puzzle(s, c);


    printf("%s\n", ans.data());
    return 0;
}
*/

Compilation message (stderr)

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:117:17: warning: unused variable 't1' [-Wunused-variable]
  117 |             int t1=0;
      |                 ^~
paint.cpp:17:9: warning: unused variable 'crni' [-Wunused-variable]
   17 |     int crni[n];
      |         ^~~~

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