Submission #195644

#	Time	Username	Problem	Language	Result	Execution time	Memory
195644		oscarsierra12	Paint By Numbers (IOI16_paint)	C++14	90 / 100	2071 ms	198048 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std ;

const int N = 2e5+2 ;

int dp [ N ][ 102 ][2];
int acc [ N ] ;
vector<int> C ;
int couldW [N], couldB[N] ;
string S ;
int posib [ N ][ 102 ];
int tam1, tam2 ;

int solve ( int i, int clue, int flag ) {
    if ( clue == tam1 && i <= tam2 ) {
        int can = 1 ;
        for ( int j = i ; j < tam2 ; ++j )
            if ( S[j] == 'X' ) can = 0;
        if ( can ) {
            for ( int j = i ; j < tam2 ; ++j )
                couldW[j] = 1 ;
        }
        return can ;
    }
    if ( i >= tam2 ) return 0 ;
    auto &rf = dp[i][clue][flag] ;
    if ( rf != -1 ) return rf ;
    rf = 0 ;
    if ( !flag && S[i] == 'X' ) return 0 ;
    if ( S[i] != 'X' && solve(i+1, clue,1)  ) {
        couldW[i] = 1 ;
        rf = 1 ;
    }
    if ( flag && acc[i+C[clue]-1] - (i?acc[i-1]:0) == 0 && solve ( i+C[clue], clue+1, 0 ) ) {
        posib[i][clue] = 1;
        rf = 1;
    }
    return rf ;
}

std::string solve_puzzle(std::string s, std::vector<int> c) {
    C = c ;
    S = s ;
    memset ( dp, -1, sizeof dp ) ;
    tam1 = c.size() ;
    tam2 = s.size() ;
    for ( int i = 0 ; i < tam2 ; ++i ) {
        if ( i ) acc[i] += acc[i-1] ;
        acc[i] += (s[i]=='_');
    }
    solve ( 0, 0,1 ) ;
    string ans ;
    int id = 0 ;
    for ( int i = 0 ; i < tam2 ; ++i ) {
        id = max ( id, i ) ;
        for ( int j = 0 ; j < tam1 ; ++j ) {
            if ( posib[i][j] ) {
               // cout << "its posible " << i << ' ' << j << '\n' ;
                for ( ; id < i + c[j] ; ++id )
                    couldB[id] = 1;
            }
        }
    }
    for ( int i = 0 ; i < tam2 ; ++i ) {
        if ( s[i] != '.' ) ans.push_back (s[i]) ;
        else {
            if ( couldB[i] && couldW[i] ) ans.push_back ('?') ;
            else if ( couldB[i] ) ans.push_back ('X');
            else ans.push_back ('_') ;
        }
    }
    return ans ;
}

• 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: 0 / 10