Submission #761130

#	Time	Username	Problem	Language	Result	Execution time	Memory
761130		raysh07	Paint By Numbers (IOI16_paint)	C++17	100 / 100	205 ms	102452 KiB

paint

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

int n, k;
const int N = 2e5 + 69;
const int K = 102;
bool dp1[N][K][2];
bool dp2[N][K][2];
int p[N];
bool b1[N], b2[N];
bool fin[N][K]; //can you finish the j'th thing at i
int cnt;

string solve_puzzle(string s, vector<int> c) {
    n = s.length();
    k = c.size();
    s = "0" + s;
    
    for (int i = 1; i <= n; i++){
        p[i] = p[i - 1];
        if (s[i] == '_') p[i]++;
    }
    
    c.push_back(0);
    for (int i = k; i > 0; i--) c[i] = c[i - 1];
    
    dp1[0][0][0] = true;
    for (int i = 1; i <= n; i++){
        if (s[i] != 'X'){
            for (int j = 0; j <= k; j++){
                dp1[i][j][0] |= dp1[i - 1][j][0] | dp1[i - 1][j][1];
            }
        }
        for (int j = 1; j <= k; j++){
            if (i >= c[j] && p[i] == p[i - c[j]]){
                dp1[i][j][1] |= dp1[i - c[j]][j - 1][0];
            }
        }
        
        // cout << i << "\t";
        // for (int j = 0; j <= k; j++){
        //     cout << dp1[i][j][0] << " " << dp1[i][j][1] << "\t";
        // }
        // cout << "\n";
    }
    
    dp2[n + 1][k + 1][0] = true;
    for (int i = n; i >= 1; i--){
        if (s[i] != 'X'){
            for (int j = 1; j <= k + 1; j++){
                dp2[i][j][0] |= dp2[i + 1][j][0] | dp2[i + 1][j][1];
            }
        }
        for (int j = 1; j <= k; j++){
            if (i + c[j] <= n + 1 && p[i - 1] == p[i + c[j] - 1]){
                dp2[i][j][1] |= dp2[i + c[j]][j + 1][0];
            }
        }
    }
    
    string ans = "";
    
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= k; j++){
            if (dp1[i][j][1] && dp2[i + 1][j + 1][0]) fin[i][j] = true;
        }
    }
    
    for (int i = 1; i <= n; i++){
        for (int j = 0; j <= k; j++){
            if (dp1[i][j][0] && dp2[i][j + 1][0]){
                b1[i] = true;
            }
        }
        
        // for (int j = 1; j <= k; j++){
        //     for (int finish = i; finish <= min(n, i + c[j] - 1); finish++){
        //         if (dp1[finish][j][1] && dp2[finish + 1][j + 1][0]) b2[i] = true;
        //     }
        // }
        
        // if (b1[i] && b2[i]) ans += '?';
        // else if (b1[i]) ans += '_';
        // else ans += 'X';
    }
    
    for (int i = n; i >= 1; i--){
        for (int j = 1; j <= k; j++){
            if (fin[i][j]) cnt++;
            
            if (i + c[j] <= n){
                if (fin[i + c[j]][j]) cnt--;
            }
        }
        
        if (cnt) b2[i] = true;
    }
    
    for (int i = 1; i <= n; i++){
        if (b1[i] && b2[i]) ans += '?';
        else if (b1[i]) ans += '_';
        else ans += 'X';
    }
    
    return ans;
}

// int main(){
//     string s; cin >> s;
//     int m; cin >> m;
//     vector <int> a(m);
//     for (auto &x : a) cin >> x;
    
//     cout << solve_puzzle(s, a);
//     return 0;
// }

• 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