Submission #1210236

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210236		onbert	Paint By Numbers (IOI16_paint)	C++20	32 / 100	0 ms	328 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5, maxk = 105, INF = 1e9;
int n, k;
bool dp[maxn][maxk][2];
int dpsum[maxn][maxk][2];


bool ansb[maxn], answ[maxn];

bool qry(int il, int ir, int j, int ii) {
    if (il > ir) return 0;
    if (ii == 0) {
        int val = dpsum[ir][j][ii];
        if (il-1 >= 0) val -= dpsum[il-1][j][ii];
        return val;
    } else if (ii == 1) {
        int val = dpsum[il][j][ii];
        if (ir+1 <= n+1) val -= dpsum[ir+1][j][ii];
        return val;
    }
    return 69420;
}

string solve_puzzle(string s, vector<int> c) {
    n = s.size(), k = c.size();
    c.push_back(0);
    for (int i=k;i>=1;i--) swap(c[i-1], c[i]);
    c.push_back(0);
    s = '_' + s;
    int lastw[n+1], lastb[n+1];
    lastw[0] = 0, lastb[0] = 0;
    for (int i=1;i<=n;i++) {
        lastw[i] = lastw[i-1], lastb[i] = lastb[i-1];
        if (s[i] == 'X') lastb[i] = i;
        if (s[i] == '_') lastw[i] = i;
    }
    dp[0][0][0] = dpsum[0][0][0] = 1;
    for (int i=1;i<=k;i++) dp[0][i][0] = dpsum[0][i][0] = 0;
    for (int i=1;i<=n;i++) {
        int w = lastw[i];
        dp[i][0][0] = (lastb[i] == 0);
        dpsum[i][0][0] = dpsum[i-1][0][0] + dp[i][0][0];
        for (int j=1;j<=k+1;j++) {
            int pos = i - c[j];
            dp[i][j][0] = (i - lastw[i] >= c[j] && ((pos == 0 && j-1 == 0) || (pos != 0 && qry(lastb[pos], pos - 1, j-1, 0))));
            dpsum[i][j][0] = dp[i-1][j][0] + dp[i][j][0];
        }
    }

    
    int nextb[n+2], nextw[n+2];
    nextb[n+1] = nextw[n+1] = n+1;
    for (int i=n;i>=1;i--) {
        nextw[i] = nextw[i+1], nextb[i] = nextb[i+1];
        if (s[i] == 'X') nextb[i] = i;
        if (s[i] == '_') nextw[i] = i;
    }
    dp[n+1][k+1][1] = dpsum[n+1][k+1][1] = 1;
    for (int i=1;i<=k;i++) dp[n+1][i][1] = dpsum[n+1][i][1] = 0;
    for (int i=n;i>=1;i--) {
        int w = nextw[i];
        dp[i][k+1][1] = (nextb[i] == n+1);
        dpsum[i][k+1][1] = dpsum[i+1][k+1][1] + dp[i][k+1][1];
        for (int j=0;j<=k;j++) {
            int pos = i + c[j];
            dp[i][j][1] = (nextw[i] - i >= c[j] && ((pos == n+1 && j+1 == k+1) || (pos != n+1 && qry(pos + 1, nextb[pos], j+1, 1))));
            dpsum[i][j][1] = dp[i+1][j][1] + dp[i][j][1];
        }
    }

    // for (int j=0;j<=k+1;j++) {
    //     for (int i=0;i<=n+1;i++) cout << dp[i][j][0] << " "; cout << endl;
    // }
    // cout << endl;

    // for (int j=0;j<=k+1;j++) {
    //     for (int i=0;i<=n+1;i++) cout << dp[i][j][1] << " "; cout << endl;
    // }
    // cout << endl;


    for (int i=1;i<=n;i++) for (int j=0;j<=k+1;j++) {
        if (i - c[j] + 1 >= 1) dp[i][j][0] &= dp[i - c[j] + 1][j][1];
        dpsum[i][j][0] = dpsum[i-1][j][0] + dp[i][j][0];
    }

    for (int i=n;i>=1;i--) for (int j=0;j<=k+1;j++) {
        if (i + c[j] - 1 <= n) dp[i][j][1] &= dp[i + c[j] - 1][j][0];
        dpsum[i][j][1] = dpsum[i+1][j][1] + dp[i][j][1];
    }

    // for (int j=0;j<=k+1;j++) {
    //     for (int i=0;i<=n+1;i++) cout << dp[i][j][0] << " "; cout << endl;
    // }
    // cout << endl;

    // for (int j=0;j<=k+1;j++) {
    //     for (int i=0;i<=n+1;i++) cout << dp[i][j][1] << " "; cout << endl;
    // }
    // cout << endl;

    for (int i=1;i<=n;i++) {
        answ[i] = ansb[i] = 0;
        for (int j=0;j<=k;j++) answ[i] |= (dpsum[i-1][j][0] && dpsum[i+1][j+1][1]);
        for (int j=1;j<=k;j++) ansb[i] |= qry(i, min(i + c[j] - 1, n), j, 0);
    }

    // for (int i=1;i<=n;i++) cout << answ[i] << " "; cout << endl;
    // for (int i=1;i<=n;i++) cout << ansb[i] << " "; cout << endl;

    string ans;
    for (int i=1;i<=n;i++) {
        if (answ[i] && ansb[i]) ans += '?';
        else if (answ[i]) ans += '_';
        else if (ansb[i]) ans += 'X';
    }
    return ans;
}

Compilation message (stderr)

paint.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
paint_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

• 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