Submission #105782

#	Time	Username	Problem	Language	Result	Execution time	Memory
105782		RezwanArefin01	Paint By Numbers (IOI16_paint)	C++17	100 / 100	380 ms	45492 KiB

paint

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

const int N = 2e5 + 5; 
bool f[N][105], g[N][105], can_b[N], can_w[N]; 
int c[105], black[N], white[N], t[N], n, k;
    
string solve_puzzle(string s, vector<int> _c) {

    n = s.size(), k = _c.size(); 
    copy(_c.begin(), _c.end(), c + 1); 
    s = "." + s + "."; 

    for(int i = 1; i <= n; ++i) {
        black[i] = black[i - 1] + (s[i] == 'X'); 
        white[i] = white[i - 1] + (s[i] == '_'); 
    } 
    white[n + 1] = white[n]; 


    f[0][0] = 1; 
    for(int i = 1; i <= n; ++i) {
        f[i][0] = black[i] == 0; 
        for(int j = 1; j <= k; ++j) {
            bool w = f[i - 1][j]; 
            bool b = (i >= c[j]) && (s[i - c[j]] != 'X') && (white[i] == white[i - c[j]]) 
                    && (i > c[j] ? f[i - c[j] - 1][j - 1] : (j == 1)); 
            f[i][j] = s[i] == '_' ? w : s[i] == 'X' ? b : (w | b); 
        }
    }

    g[n + 1][k + 1] = g[n + 2][k + 1] = 1; 
    for(int i = n; i >= 1; --i) {
        g[i][k + 1] = black[n] == black[i - 1]; 
        for(int j = k; j >= 1; --j) {
            bool w = g[i + 1][j]; 
            bool b = (n - i + 1 >= c[j]) && (s[i + c[j]] != 'X') && (white[i - 1] == white[i + c[j] - 1])  
                    && g[i + c[j] + 1][j + 1]; 
            g[i][j] = s[i] == '_' ? w : s[i] == 'X' ? b : (w | b); 
        }
    }

    for(int i = 1; i <= n; ++i) {
        if(s[i] == '_') can_w[i] = 1; 
        else {
            for(int c = 0; c <= k && !can_w[i]; ++c) {
                can_w[i] |= f[i - 1][c] && g[i + 1][c + 1]; 
            }
        }
        for(int j = 1; j <= k; ++j) {
            if(i >= c[j] && s[i - c[j]] != 'X' && s[i + 1] != 'X' && white[i] == white[i - c[j]] &&
               (i > c[j] ? f[i - c[j] - 1][j - 1] : (j == 1)) && g[i + 2][j + 1]) {
                t[i - c[j] + 1]++; t[i + 1]--; 
            }
        }
    }

    for(int i = 1; i <= n; ++i) {
        t[i] += t[i - 1]; 
        can_b[i] = t[i] > 0; 
    }

    string ans = ""; 
    for(int i = 1; i <= n; ++i) {
        if(s[i] != '.') ans += s[i]; 
        else {
            if(can_w[i] && can_b[i]) ans += '?'; 
            else ans += (can_w[i] ? '_' : 'X');
        }
    }

    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