Submission #195678

#	Time	Username	Problem	Language	Result	Execution time	Memory
195678		oscarsierra12	Paint By Numbers (IOI16_paint)	C++14	100 / 100	1083 ms	257672 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 ], acc2[N] ;
vector<int> C ;
int couldW [N], couldB[N] ;
string S ;
int posib [ N ][ 102 ];
int tam1, tam2 ;
int ult[N] ;

int solve ( int i, int clue, int flag ) {
    if ( clue == tam1 && i <= tam2 ) {
        int can = (acc2[tam2-1] - (i?acc2[i-1]:0) == 0) ;
        ult[i] = can ;
        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], acc2[i] += acc2[i-1] ;
        acc[i] += (s[i]=='_');
      	acc2[i] += (s[i]=='X') ;
    }
    solve ( 0, 0,1 ) ;
    string ans ;
    int id = 0 ;
    int curMx = 0 ;
    for ( int i = 0 ; i < tam2 ; ++i ) { 
    	curMx = max ( curMx, ult[i] ) ;
        couldW[i] = max ( couldW[i], curMx ) ;
    }
    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: 10 / 10