Submission #563451

#	Time	Username	Problem	Language	Result	Execution time	Memory
563451		elazarkoren	Paint By Numbers (IOI16_paint)	C++17	100 / 100	315 ms	60584 KiB

paint

#include <bits/stdc++.h>
#include "paint.h"
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;

const int MAX_N = 2e5 + 5;
const int MAX_K = 105;

bool dp[MAX_N][MAX_K];
int add_x[MAX_N];
int add_empty[MAX_N];
int nexts[MAX_N];
bool visited[MAX_N][MAX_K];
int ex;

vi c;
string s;

void Solve(int i, int j) {
    if (i < 0 || j < 0 || visited[i][j]) return;
    visited[i][j] = true;
    if (s[i] != 'X' && i && dp[i - 1][j]) {
        add_empty[i]++;
        add_empty[i + 1]--;
        Solve(i - 1, j);
    }
    int last = i - c[j];
    bool b = nexts[last + 1] > i && (last < 0 || s[last] != 'X');
    if (b && !j && ex > last) {
        add_x[last + 1]++, add_x[i + 1]--;
        add_empty[0]++, add_empty[last + 1]--;
    } else if (b && j && dp[last - 1][j - 1]) {
        add_x[last + 1]++, add_x[i + 1]--;
        add_empty[last]++, add_empty[last + 1]--;
        Solve(last - 1, j - 1);
    }
}

int n, k;

string solve_puzzle(string S, vi C) {
    s = S, c = C;
    n = s.size(), k = c.size();
    nexts[n] = n;
    ex = n;
    for (int i = n - 1; i >= 0; i--) {
        nexts[i] = (s[i] == '_' ? i : nexts[i + 1]);
        if (s[i] == 'X') ex = i;
    }
    for (int i = 0; i < n; i++) {
        if (s[i] != 'X' && i) {
            for (int j = 0; j < k; j++) {
                dp[i][j] = dp[i - 1][j];
            }
        }
        if (s[i] == '_') continue;
        for (int j = 0, sum = -1; j < k; j++) {
            sum += c[j] + 1;
            if (sum > i + 1) break;
            if (dp[i][j]) continue;
            int last = i - c[j];
            bool b = nexts[last + 1] > i && (last < 0 || s[last] != 'X');
            if (b && !j) {
                dp[i][j] = ex > last;
            } else if (b && dp[last - 1][j - 1]) {
                dp[i][j] = true;
            }
        }
    }
    Solve(n - 1, k - 1);
    string ans(n, '?');
    for (int i = 0, x = 0, em = 0; i < n; i++) {
        x += add_x[i], em += add_empty[i];
        if (x && !em) ans[i] = 'X';
        else if (!x && em) ans[i] = '_';
    }
    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