Submission #195643

#	Time	Username	Problem	Language	Result	Execution time	Memory
195643		oscarsierra12	Paint By Numbers (IOI16_paint)	C++14	90 / 100	2063 ms	198100 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 tam ;

int solve ( int i, int clue, int flag ) {
    if ( clue == C.size() && i <= S.size() ) {
        int can = 1 ;
        for ( int j = i ; j < S.size() ; ++j )
            if ( S[j] == 'X' ) can = 0;
        if ( can ) {
            for ( int j = i ; j < S.size() ; ++j )
                couldW[j] = 1 ;
        }
        return can ;
    }
    if ( i >= S.size() ) 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 ) ;
    for ( int i = 0 ; i < s.size() ; ++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 < s.size() ; ++i ) {
        id = max ( id, i ) ;
        for ( int j = 0 ; j < c.size() ; ++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 < s.size() ; ++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 ;
}

Compilation message (stderr)

paint.cpp: In function 'int solve(int, int, int)':
paint.cpp:16:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if ( clue == C.size() && i <= S.size() ) {
          ~~~~~^~~~~~~~~~~
paint.cpp:16:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if ( clue == C.size() && i <= S.size() ) {
                              ~~^~~~~~~~~~~
paint.cpp:18:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for ( int j = i ; j < S.size() ; ++j )
                           ~~^~~~~~~~~~
paint.cpp:21:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for ( int j = i ; j < S.size() ; ++j )
                               ~~^~~~~~~~~~
paint.cpp:26:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if ( i >= S.size() ) return 0 ;
          ~~^~~~~~~~~~~
paint.cpp: In function 'std::__cxx11::string solve_puzzle(std::__cxx11::string, std::vector<int>)':
paint.cpp:46:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for ( int i = 0 ; i < s.size() ; ++i ) {
                       ~~^~~~~~~~~~
paint.cpp:53:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for ( int i = 0 ; i < s.size() ; ++i ) {
                       ~~^~~~~~~~~~
paint.cpp:55:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for ( int j = 0 ; j < c.size() ; ++j ) {
                           ~~^~~~~~~~~~
paint.cpp:63:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for ( int i = 0 ; i < s.size() ; ++i ) {
                       ~~^~~~~~~~~~

• 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