Submission #1293720

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293720		vincentbucourt1	Paint By Numbers (IOI16_paint)	C++20	100 / 100	877 ms	34220 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;

int N, Q;
enum INFO {ON, OFF, BOTH};
vector<INFO> info; // NOTE: 1-idx
// NOTE: blocks: 1-idx
vector<int> prefOff; // NOTE: exc
vector<vector<bool>> prefDP, suffDP; // NOTE: [exc][exc]
vector<int> diffOn, diffOff; // NOTE: [l, r) updates

int cntOff (int l, int r) {
    return prefOff[r+1] - prefOff[l];
}

std::string solve_puzzle(std::string specified, std::vector<int> blocks) {
    N = (int)specified.size();
    Q = (int)blocks.size();
    info.assign(N+20, BOTH);
    for (int i = 0; i < N; i++) {
        if (specified[i] == 'X') {
            info[i+1] = ON;
        }
        else if (specified[i] == '_') {
            info[i+1] = OFF;
        }
        else {
            info[i+1] = BOTH;
        }
    }
    // cerr << "info: ";
    // for (int i = 1; i <= N; i++) cerr << info[i] << " ";
    // cerr << "\n";
    vector<int> tempBlocks(Q+20);
    for (int q = 0; q < Q; q++) {
        tempBlocks[q+1] = blocks[q];
    }
    swap(blocks, tempBlocks);

    prefOff.assign(N+20, 0);
    for (int i = 1; i <= N; i++) {
        prefOff[i+1] = prefOff[i] + (info[i] == OFF);
    }
    // cerr << "prefOff: ";
    // for (int i = 1; i <= N; i++) cerr << prefOff[i] << " ";
    // cerr << "\n";

    prefDP.assign(N+20, vector<bool>(Q+20, false));
    prefDP[1][1] = true;
    for (int i = 1; i <= N; i++) {
        for (int q = 1; q <= Q+1; q++) {
            if (prefDP[i][q]) {
                if (info[i] != ON) {
                    prefDP[i+1][q] = true;
                }
                if (q <= Q) {
                    int blockOn = blocks[q];
                    // NOTE: [i, i + blockOn - 1]: ON, [i + blockOn, i + blockOn]: OFF
                    if (i + blockOn - 1 <= N && cntOff(i, i + blockOn - 1) == 0 && info[i + blockOn] != ON) {
                        prefDP[i + blockOn + 1][q+1] = true;
                    }
                }
            }
        }
    }

    suffDP.assign(N+20, vector<bool>(Q+20, false));
    suffDP[N][Q] = true;
    suffDP[N+1][Q] = true;
    for (int i = N; i >= 1; i--) {
        for (int q = Q; q >= 0; q--) {
            if (suffDP[i][q]) {
                if (info[i] != ON) {
                    suffDP[i-1][q] = true;
                }
                int blockOn = blocks[q];
                // NOTE: [i - blockOn + 1, i]: ON
                if (q >= 1 && i == N && cntOff(i - blockOn + 1, i) == 0) {
                    suffDP[i - blockOn][q-1] = true;
                }
                // NOTE: [i - blockOn, i - 1]: ON, [i, i]: OFF
                if (q >= 1 && 1 <= i - blockOn && cntOff(i - blockOn, i - 1) == 0 && info[i] != ON) {
                    suffDP[i - blockOn - 1][q-1] = true;
                }
            }
        }
    }

    cerr << "prefDP tests:\n";
    cerr << "   exp: 1, got: " << prefDP[8][2] << "\n";
    cerr << "suffDP tests:\n";
    cerr << "   exp: 1, got: " << suffDP[1][0] << "\n";
    
    diffOn.assign(N+20, 0);
    diffOff.assign(N+20, 0);
    cerr << "inters:\n";
    for (int i = 1; i <= N; i++) {
        for (int q = 1; q <= Q+1; q++) {
            // NOTE: [i, i]: OFF
            if (prefDP[i][q] && info[i] != ON && suffDP[i][q-1]) {
                // cerr << "    " << i << " " << q << "\n";
                diffOff[i]++, diffOff[i+1]--;
            }
            if (q <= Q) {
                int blockOn = blocks[q];
                // NOTE: [i, i + blockOn - 1]: ON, [i + blockOn, i + blockOn]: OFF
                if (prefDP[i][q] && i + blockOn - 1 <= N && cntOff(i, i + blockOn - 1) == 0 && info[i + blockOn] != ON && suffDP[i + blockOn][q]) {
                    // cerr << "   " << i << " " << i + blockOn - 1 << "\n";
                    diffOn[i]++, diffOn[i + blockOn]--;
                    diffOff[i + blockOn]++, diffOff[i + blockOn + 1]--;
                }
            }
        }
    }

    for (int i = 1; i <= N; i++) {
        diffOn[i+1] += diffOn[i];
        diffOff[i+1] += diffOff[i];
        if (info[i] == ON) diffOn[i] = 1;
        if (info[i] == OFF) diffOff[i] = 1;
    }

    cerr << "diffOn:  ";
    for (int d : diffOn) cerr << d << " ";
    cerr << "\ndiffOff: ";
    for (int d : diffOff) cerr << d << " ";
    cerr << "\n";

    string ans;
    for (int i = 1; i <= N; i++) {
        if (diffOn[i] && diffOff[i]) {
            ans += '?';
        }
        else if (diffOn[i] && !diffOff[i]) {
            ans += 'X';
        }
        else if (!diffOn[i] && diffOff[i]) {
            ans += '_';
        }
        else { // shouldnt happen
            assert(false);
        }
    }

    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