Submission #1191112

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191112		jasonic	Paint By Numbers (IOI16_paint)	C++20	59 / 100	87 ms	167116 KiB

paint

/*

cnt[i][j] = how many ways to use the first j blocks such that they fit in the first i of the row

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 cnt2[mxn][mxk];
int times[mxn];
int cantplace[mxn];
int haveplace[mxn];
int n, k;
int lastX, firstX;

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

    memset(cnt, 0, sizeof(cnt));
    memset(cnt2, 0, sizeof(cnt2));
    memset(haveplace, 0, sizeof(haveplace));
    memset(cantplace, 0, sizeof(cantplace));
    memset(times, 0, sizeof(times));
    firstX = INT_MAX;
    lastX = INT_MIN;

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

    cerr << firstX << ' ' << lastX << '\n';

    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 i = 1; i <= k; i++) {
        int blockLength = c[i-1];
        
        for(int right = 1; right <= n; right++) {
            int left = right - blockLength + 1; // this is where the "block of X" will get put

            if(haveplace[left-1] == haveplace[right]) cnt[right][i] += cnt[right-1][i]; // just append

            if(left < 1) continue;

            // one indexed everything LOL
            if(cantplace[right] == cantplace[left - 1]) { // no "_" in the range
                if(left >= 2) if(s[left - 2] == 'X') {
                    cerr << "exit1\n";
                    cerr << i << ' ' << right << ' ' << cnt[right][i] << '\n';
                    continue;
                }
                if(right < n) if(s[right] == 'X') {
                    cerr << "exit2\n";
                    cerr << i << ' ' << right << ' ' << cnt[right][i] << '\n';
                    continue;
                }
                if(i == k) if (right < lastX) { // last element (or earlier) must "hit" hit the last X
                    cerr << "exit3\n";
                    cerr << i << ' ' << right << ' ' << cnt[right][i] << '\n';
                    continue;
                }

                cnt[right][i] += cnt[max(0, left-2)][i-1];
            }

            cerr << max(0, left-2) << '\n';

            cerr << i << ' ' << right << ' ' << cnt[right][i] << '\n';
            
            if(s[left-1] == 'X') {
                cerr << "passed an X break\n";
                break;
            }
        }
    }

    cerr << "\n\n\n\n";

    cnt2[n+1][k+1] = 1;
    for(int i = n; i >= 1 && s[i-1] != 'X'; i--) cnt2[i][k+1] = 1;

    // other way!
    for(int i = k; i >= 1; i--) {
        int blockLength = c[i-1];
        
        for(int left = n; left >= 1; left--) {
            int right = left + blockLength - 1;
            
            cerr << "append test " << left+1 << ' ' << i << ' ' << cnt2[left+1][i] << '\n';
            
            if(haveplace[left-1] == haveplace[right])cnt2[left][i] += cnt2[left+1][i]; // just append

            cerr << "calculating " << left << ' ' << right << '\n';

            if(right >= n+1) continue;

            cerr << "continuing  " << left << ' ' << right << '\n';


            if(cantplace[left-1] == cantplace[right]) {
                if(left >= 2) if(s[left - 2] == 'X') {
                    cerr << "exit1\n";
                    cerr << i << ' ' << right << ' ' << cnt2[left][i] << '\n';
                    continue;
                }
                if(right < n) if(s[right] == 'X') {
                    cerr << "exit2\n";
                    cerr << i << ' ' << right << ' ' << cnt2[left][i] << '\n';
                    continue;
                }
                if(i == 1) if (left < firstX) { // last element (or earlier) must "hit" hit the first X
                    cerr << "exit3\n";
                    cerr << i << ' ' << right << ' ' << cnt2[left][i] << '\n';
                    continue;
                }
                cnt2[left][i] += cnt2[min(n+1, right+2)][i+1];
            }

            cerr << i << ' ' << left << ' ' << right << ' ' << cnt2[left][i] << '\n';

            if(s[right-1] == 'X') {
                cerr << "passed an X break\n";
                break;
            }
        }
    }

    for(int i = 1; i <= k; i++) {
        int blockSize = c[i-1];
        for(int left = 1; left <= n; left++) {
            int right = left + blockSize - 1;
            if(right > n) continue;

            if(cantplace[left-1] != cantplace[right]) continue;
            if(left >= 2) if(s[left-2] == 'X') continue;
            if(right < n) if(s[right] == 'X') continue;

            int timesUsed = cnt[max(0, left-2)][i-1] * cnt2[min(n+1, right+2)][i+1];
            
            times[left-1] += timesUsed;
            if(right < n) times[right] -= timesUsed;
        }
    }

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