Submission #441722

#	Time	Username	Problem	Language	Result	Execution time	Memory
441722		FEDIKUS	Paint By Numbers (IOI16_paint)	C++17	100 / 100	428 ms	46784 KiB

paint

#include "paint.h"

#include <cstdlib>
#include<bits/stdc++.h>

using namespace std;

typedef string str;

const int maxn=2e5+10;
const int maxk=110;

int w[maxn];
int b[maxn];
bool moze[maxn][maxk];
bool mozer[maxn][maxk];

bool mw[maxn];
int mb[maxn];

str solve_puzzle(str s, vector<int> c) {
    str ret=s;
    int n=s.size();
    int k=c.size();
    for(int i=0;i<n;i++){
        if(i>0){
            w[i]=w[i-1];
            b[i]=b[i-1];
        }
        if(s[i]=='_') w[i]++;
        else if(s[i]=='X') b[i]++;
    }
    ///napred
    for(int i=0;i<=n;i++){
        for(int j=0;j<=k;j++){
            if(j==0){
                if(b[i-1]==0) moze[i][j]=true;
                else moze[i][j]=false;
                continue;
            }
            moze[i][j]=false;
            if(s[i-1]=='X' || s[i-1]=='.'){
                if(i>=c[j-1] && w[i-1]==(i>c[j-1]+1 ? w[i-1-c[j-1]]:0) && (i<c[j-1]+1 || s[i-c[j-1]-1]!='X'))
                    if(i-c[j-1]-1==-1){
                        if(j-1==0) moze[i][j]=true;
                    }else moze[i][j]|=moze[i-c[j-1]-1][j-1];
            }
            if(s[i-1]=='_' || s[i-1]=='.'){
                moze[i][j]|=moze[i-1][j];
            }
        }
        //for(int j=0;j<=k;j++) cout<<i<<" "<<j<<" "<<int(moze[i][j])<<"\n";
    }//cout<<"\n\n";
    ///nazad
    for(int i=n;i>=0;i--){
        for(int j=k;j>=0;j--){
            if(j==k){
                if(i==n || (i>0 ? b[i-1]:0)==b[n-1]) mozer[i][j]=true;
                else mozer[i][j]=false;
                continue;
            }
            mozer[i][j]=false;
            if(s[i]=='X' || s[i]=='.'){
                if(i+c[j]<=n && w[i]==w[i+c[j]-1] && (n<=i+c[j] || s[i+c[j]]!='X'))
                    if(i+c[j]+1==n+1){
                        if(j+1==k) mozer[i][j]=true;
                    }else mozer[i][j]|=mozer[i+c[j]+1][j+1];
            }
            if(s[i]=='_' || s[i]=='.'){
                mozer[i][j]|=mozer[i+1][j];
            }
        }
        //for(int j=0;j<=k;j++) cout<<i<<" "<<j<<" "<<int(mozer[i][j])<<"\n";
    }
    for(int i=0;i<n;i++){
        mw[i]=false;
        if(s[i]!='X'){
            for(int j=0;j<=k;j++){
                if(moze[i][j] && mozer[i+1][j]) mw[i]=true;
            }
        }
        for(int j=0;j<k;j++){
            if(i+c[j]<=n &&
               (i==0 || s[i-1]!='X') &&
               (i+c[j]>=n || s[i+c[j]]!='X') &&
               ((i>0 ? w[i-1]:0)==w[i+c[j]-1]) &&
               ((i-1==-1 && j==0) || moze[i-1][j]) &&
               ((i+c[j]+1==n+1 && j+1==k) || mozer[i+c[j]+1][j+1])){
                mb[i]++;
                //cout<<i<<" "<<j<<" ovo\n";
                if(i+c[j]<n) mb[i+c[j]]--;
            }
        }
    }
    int tren=0;
    for(int i=0;i<n;i++){
        tren+=mb[i];
        mb[i]=tren;
    }
    for(int i=0;i<n;i++){
        if(mw[i] && mb[i]) ret[i]='?';
        else if(mw[i]) ret[i]='_';
        else ret[i]='X';
    }
    return ret;
}
/*
..._._....
1 3
*/

Compilation message (stderr)

paint.cpp: In function 'str solve_puzzle(str, std::vector<int>)':
paint.cpp:43:19: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   43 |                 if(i>=c[j-1] && w[i-1]==(i>c[j-1]+1 ? w[i-1-c[j-1]]:0) && (i<c[j-1]+1 || s[i-c[j-1]-1]!='X'))
      |                   ^
paint.cpp:64:19: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   64 |                 if(i+c[j]<=n && w[i]==w[i+c[j]-1] && (n<=i+c[j] || s[i+c[j]]!='X'))
      |                   ^

• 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