Submission #1129507

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129507		yellowtoad	Paint By Numbers (IOI16_paint)	C++20	100 / 100	320 ms	103100 KiB

paint

#include "paint.h"
#include <iostream>
#include <cstdlib>
using namespace std;

int n, m, ps[200010], ok[200010][2], d[200010];
bool dp[200010][110][2], vis[200010][110][2];
string ans;
vector<int> c;

void dfs(int i, int j, int k) {
    if (vis[i][j][k] || !dp[i][j][k] || (i == 0)) return;
    vis[i][j][k] = 1;
    if (k == 0) {
        ok[i][0] = 1;
        dfs(i-1,j,0);
        dfs(i-1,j,1);
    } else {
        d[i+1]--;
        d[i-c[j-1]+1]++;
        dfs(i-c[j-1],j-1,0);
    }
}

std::string solve_puzzle(std::string s, std::vector<int> C) {
    c = C; n = s.length(); m = c.size();
    s = " "+s;
    for (int i = 1; i <= n; i++) ps[i] = ps[i-1]+(s[i] == '_');
    dp[0][0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            if (s[i] != 'X') dp[i][j][0] = max(dp[i-1][j][0],dp[i-1][j][1]);
            if ((s[i] != '_') && (j != 0) && (ps[i]-ps[i-c[j-1]] == 0)) dp[i][j][1] = dp[i-c[j-1]][j-1][0]; 
        }
    }
    dp[n+1][m][0] = max(dp[n][m][0],dp[n][m][1]);
    dfs(n+1,m,0);
    for (int i = 1; i <= n; i++) {
        d[i] += d[i-1];
        if (d[i]) ok[i][1] = 1;
    }
    for (int i = 1; i <= n; i++) {
        if (ok[i][0] && ok[i][1]) ans += "?";
        else if (ok[i][0]) ans += "_";
        else 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: 27 / 27
• Subtask 5: 21 / 21
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10