Submission #596296

#	Time	Username	Problem	Language	Result	Execution time	Memory
596296		stevancv	Paint By Numbers (IOI16_paint)	C++14	100 / 100	409 ms	175244 KiB

paint

#include <bits/stdc++.h>
#include "paint.h"
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 5e5 + 2;
const int mod = 1e9 + 7;
string solve_puzzle(string s, vector<int> c) {
    int n = s.size(); int k = c.size();
    c.push_back(0);
    for (int i = k; i >= 1; i--) c[i] = c[i - 1];
    s = "1" + s;
    vector<int> pref(n + 1);
    for (int i = 1; i <= n; i++) pref[i] = pref[i - 1] + (s[i] == '_');
    vector<vector<int>> dp1(n + 1, vector<int>(k + 1));
    dp1[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= k; j++) {
            if (s[i] != 'X') dp1[i][j] |= dp1[i - 1][j];
            int pi = i - c[j] - 1;
            if (pi >= 0 && j >= 1 && s[i] != 'X' && pref[i - 1] == pref[pi]) dp1[i][j] |= dp1[pi][j - 1];
        }
    }
    vector<vector<int>> dp2(n + 2, vector<int>(k + 2));
    dp2[n + 1][k + 1] = 1;
    for (int i = n; i >= 1; i--) {
        for (int j = 1; j <= k + 1; j++) {
            if (s[i] != 'X') dp2[i][j] |= dp2[i + 1][j];
            int pi = i + c[j] + 1;
            if (pi <= n + 1 && j <= k && s[i] != 'X' && pref[i] == pref[pi - 1]) dp2[i][j] |= dp2[pi][j + 1];
        }
    }
    vector<int> dp3(n + 2);
    for (int i = 1; i <= n; i++) {
        int w = 0;
        for (int j = 0; j <= k; j++) {
            if (dp1[i][j] && dp2[i][j + 1]) w = 1;
            if (j == 0 || i + c[j] > n + 1) continue;
            if (dp1[i - 1][j - 1] && dp2[i + c[j]][j + 1] && pref[i - 1] == pref[i + c[j] - 1]) {
                dp3[i]++;
                dp3[i + c[j]]--;
            }
        }
        dp3[i] += dp3[i - 1];
        if (w && dp3[i]) s[i] = '?';
        else if (w) s[i] = '_';
        else s[i] = 'X';
    }
    string ret;
    for (int i = 1; i <= n; i++) ret += s[i];
    return ret;
}

• 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