Submission #591426

#	Time	Username	Problem	Language	Result	Execution time	Memory
591426		Vanilla	Paint By Numbers (IOI16_paint)	C++17	32 / 100	1 ms	340 KiB

paint

#include <bits/stdc++.h>
#include "paint.h"
using namespace std;
const int maxn = 102;
vector <vector <int> > v[maxn];
int dp[maxn][maxn]; // dp[i][j] -> if you can finish i-th partition on the position j
int l[maxn];
int r[maxn];

// string solve_puzzle_0(string s, vector<int> c) {
//     int n = s.size();
//     int k = c.size();
//     string rs = s;
//     auto safe = [&] (int x, int p) {
//         if (x - p + 1 < 0) return 0;
//         for (int i = x; i >= x - p + 1; i--) {
//             if (s[i] == '_') return 0;
//         }
//         return 1;
//     };
//     for (int i = 0; i < n; i++){
//         dp[0][i] = safe(i, c[0]);
//     }
//     for (int i = 1; i < k; i++){
//         for (int j = c[i] + 1; j < n; j++){
//             dp[i][j] = (dp[i-1][j - c[i] - 1] | dp[i][j-1]) & safe(j, c[i]);
//         }
//     }
//     for (int i = k - 1; i > 0; i--){
//         for (int j = 0; j < n; j++){
//             if (dp[i][j] && (j == n-1 || !dp[i][j + 1])) {
//                 for (int l = j; l >= max(j - c[i], 0); l--) {
//                     dp[i-1][l] = 0;
//                 }
//             }
//         }
//     }
//     for (int i = 0; i < k; i++){
//         int parts = 0;
//         l[i] = r[i] = -1;
//         for (int j = 0; j < n; j++){
//             if (dp[i][j]) {
//                 if (j == 0 || !dp[i][j-1]) parts++;
//                 if (l[i] == -1) l[i] = j;
//                 r[i] = j;
//                 for (int l = j - c[i] + 1; l <= j; l++){
//                     rs[l] = '?';
//                 }
//             }
//         }
//         if (parts == 1) {
//             // cout << i << " " << l[i] << " " << r[i] << "\n";
//             // l[i] - c[i] + 1, r[i] reunion
//             // r[i] - c[i] + 1, l[i] intersection
//             for (int j = r[i] - c[i] + 1; j <= l[i]; j++) {
//                 rs[j] = 'X';
//             }
//         }
//     }
//     for (int i = 0; i < n; i++){
//         if (rs[i] == '.') rs[i] = '_';
//     }
//     // for (int i = 0; i < k; i++){
//     //     for (int j = 0; j < n; j++){
//     //         cout << dp[i][j];
//     //     }
//     //     cout << "\n";
//     // }

//     return rs;
// }

// void clear () {
//     for (int i = 0; i < maxn; i++){
//         l[i] = 1e9;
//         r[i] = -1;
//         for (int j = 0; j < maxn; j++){
//             dp[i][j] = 0;
//         }
//     }
// }

string solve_puzzle(string s, vector<int> c) {
    // s.insert(s.begin(), '_');
    // s.insert(s.end(), '_');
    int n = s.size();
    int k = c.size();
    vector <int> inc(n + 1);
    vector <int> wk (n + 1, 0);
    vector <int> blea (n + 1);
    string rs = s;
    auto find = [&] (int ps, int k, bool rev) {
        int sf = 0;
        if (rev) {
            for (int i = ps; i >= 0; i--){
                if (s[i] == '.') sf++;
                else sf = 0;
                if (sf == k) return i + sf - 1;
            }
            return -1;
        }
        for (int i = ps; i < n; i++){
            if (s[i] == '.') sf++;
            else sf = 0;
            if (sf == k) return i;
        }
        return -1;
    };
    for (int i = 0; i < k; i++) l[i] = 1e9, r[i] = -1;
    l[0] = find(0, c[0], 0);
    for (int i = 1; i < k; i++){
        l[i] = find(l[i-1] + 2, c[i], 0);
    }
    r[k-1] = find(n-1, c[k-1], 1);
    for (int i = k - 2; i >= 0; i--){
        r[i] = find(r[i + 1] - c[i + 1] - 1, c[i], 1);
    }
    for (int i = 0; i < k; i++){
        // l[i] - c[i] + 1, r[i] reunion
        // r[i] - c[i] + 1, l[i] intersection
        int lpos = -1;
        for (int j = l[i] - c[i] + 1; j <= r[i]; j++){
            inc[j]++;
            if (rs[j] == '_') {
                if (lpos != -1) {
                    for (int k = lpos; k <= j; k++){
                        blea[k] = 1;
                        if (j - lpos - 1 >= c[i]) wk[k] = 1;
                    }
                }
                lpos = j;
            }
        }
        for (int j = r[i] - c[i] + 1; j <= l[i]; j++) {
            if (rs[j] != '_') rs[j] = 'X';
        }
    }
    for (int i = 0; i < n; i++){
        if (!inc[i]) rs[i] = '_';
        else if (rs[i] == '.' && blea[i] && !wk[i]) rs[i] = '_';
        else if (i - 1 >= 0 && i + 1 < n && rs[i-1] == 'X' && rs[i + 1] == 'X' && rs[i] == '.') rs[i] = '_';
        else if (rs[i] == '.') rs[i] = '?';
    }

    return rs;
}

• Subtask 1: 7 / 7
• Subtask 2: 3 / 3
• Subtask 3: 22 / 22
• Subtask 4: 0 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10