Submission #1190946

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190946		jasonic	Paint By Numbers (IOI16_paint)	C++20	10 / 100	2077 ms	494144 KiB

paint

/*
idea: bfs each state. count the # of ways to do it at the end (:= a). then use an array to track, for each cell "okay, this is how many times this cell appears". preprocess this using a difference array for sweet sweet O(n)

for each cell, if its == 0, then its guaranteed '.'
               if its == a, then its guaranteed '#'
*/

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

#define ll long long
#define one first
#define two second
#define cerr if(0) cout

const int mxn = 200005;
const int mxk = 105;
int cnt[mxn][mxk];
int actualCnts[mxn][mxk];
int times[mxn];
int cantplace[mxn];
int haveplace[mxn];
int n, k;

string solve_puzzle(string s, vector<int> c) {
    // calculate ways
    n = s.size();
    k = c.size();

    memset(cnt, 0, sizeof(cnt));
    memset(haveplace, 0, sizeof(haveplace));
    memset(cantplace, 0, sizeof(cantplace));
    memset(times, 0, sizeof(times));

    for(int i = 0; i < n; i++) {
        if (s[i] == 'X') haveplace[i+1] += 1;
        if (s[i] == '_') cantplace[i+1] += 1;
        if(i) {haveplace[i+1] += haveplace[i]; cantplace[i+1] += cantplace[i];}
    }

    cnt[0][0] = 1;
    // dp[i][j] = dp[i + c[j]]
    for(int i = 1; i <= n && s[i-1] != 'X'; i++) cnt[i][0] = 1;

    for(int right = 0; right <= n; right++) cerr << 0 << ' ' << right << ' ' << cnt[right][0] << '\n';

    for(int i = 1; i <= k; i++) {
        int blockLength = c[i-1];
        
        for(int right = 1; right <= n; right++) {
            if (s[i] != 'X') cnt[right][i] += cnt[right-1][i]; // just append

            int left = right - blockLength; // this is where the "block of X" will get put

            if(left < 0) continue;

            // one indexed everything LOL
            if(cantplace[right] == cantplace[left]) { // no "_" in the range
                if(left != 0) if(s[left] == 'X') continue;
                cnt[right][i] += cnt[max(0, left-1)][i-1];
            }

            cerr << i << ' ' << right << ' ' << cnt[right][i] << '\n';
        }
    }

    queue<pair<int, int>> bfs;
    bfs.push({n, k});
    cerr << '\n';

    while(!bfs.empty()) {
        pair<int, int> curr = bfs.front(); bfs.pop();
        if(curr.two <= 0 or curr.one <= 0) continue;

        int left = curr.one - c[curr.two - 1];
        int right = curr.one;
        int timesUsed = cnt[curr.one][curr.two] - cnt[curr.one-1][curr.two];
        if(!timesUsed) continue;
        bfs.push({curr.one - 1, curr.two});

        cerr << left << ' ' << right << ' ' << timesUsed << '\n';

        times[left] += timesUsed;
        if(right < n) times[right] -= timesUsed;

        if(timesUsed) bfs.push({max(0, left - 1), curr.two - 1});
    }

    for(int i = 1; i < n; i++) {
        times[i] += times[i-1];
    }

    for(int i = 0; i < n; i++) cerr << times[i] << ' ';
    
    string ans;
    for(int i = 0; i < n; i++) {
        if(times[i] == 0) ans.push_back('_');
        else if(times[i] == cnt[n][k]) ans.push_back('X');
        else ans.push_back('?');
    }

    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: 0 / 22
• Subtask 4: 0 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10