Submission #598919

#	Time	Username	Problem	Language	Result	Execution time	Memory
598919		cheissmart	Paint By Numbers (IOI16_paint)	C++14	100 / 100	314 ms	85640 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 2e5 + 5, K = 105;

bool dpl[N][K][2];
bool dpr[N][K][2];
int l[N], r[N];

string solve_puzzle(string s, vi c) {
    int n = SZ(s), k = SZ(c);
    dpl[0][0][0] = 1;
    for(int i = 1; i <= n; i++) {
        if(s[i - 1] == '_') l[i] = 0;
        else l[i] = l[i - 1] + 1;
        for(int j = 0; j <= k; j++) {
            // 0
            if(s[i - 1] != 'X')
                dpl[i][j][0] |= dpl[i - 1][j][0] | dpl[i - 1][j][1];
            // 1
            if(s[i - 1] != '_' && j && c[j - 1] <= l[i])
                dpl[i][j][1] |= dpl[i - c[j - 1]][j - 1][0];
        }
    }

    dpr[n + 1][0][0] = 1;
    for(int i = n; i >= 1; i--) {
        if(s[i - 1] == '_') r[i] = 0;
        else r[i] = r[i + 1] + 1;
        for(int j = 0; j <= k; j++) {
            // 0
            if(s[i - 1] != 'X')
                dpr[i][j][0] |= dpr[i + 1][j][0] | dpr[i + 1][j][1];
            // 1
            if(s[i - 1] != '_' && j && c[k - j] <= r[i])
                dpr[i][j][1] |= dpr[i + c[k - j]][j - 1][0];
        }
    }

    string ans(n, '@');

    for(int i = 1; i <= n; i++)
        for(int j = 0; j <= k; j++)
            if(dpl[i][j][0] && dpr[i][k - j][0])
                ans[i - 1] = '_';

    vi p(n + 1);

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= k; j++) {
            if(dpl[i][j][1] && dpr[i + 1][k - j][0]) {
                int lb = i - c[j - 1] + 1, rb = i;
                p[lb - 1]++;
                p[rb]--;
            }
        }
    }
    for(int i = 0; i < n; i++) {
        if(i) p[i] += p[i - 1];
        if(p[i]) {
            if(ans[i] == '_') ans[i] = '?';
            else ans[i] = 'X';
        }
    }

    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