Submission #591318

#	Time	Username	Problem	Language	Result	Execution time	Memory
591318		Vanilla	Paint By Numbers (IOI16_paint)	C++17	7 / 100	1 ms	212 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];
int icl[maxn];

string solve_puzzle(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++){
                    icl[l] = 1;
                    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;
}

// string solve_puzzle(string s, vector<int> c) {
//     int n = s.size();
//     int k = c.size();
//     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
//         for (int j = r[i] - c[i] + 1; j <= l[i]; j++) {
//             rs[j] = 'X';
//         }
//     }
//     vector <int> ps;
//     for (int i = 0; i < n; i++){
//         if (s[i] == '_') ps.push_back(i);
//     }
//     for (int i = 0; i < ps.size() - 1; i++){
        
//     }
//     for (int i = 0; i < n; i++){
//         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: 0 / 3
• Subtask 3: 0 / 22
• Subtask 4: 0 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10