Submission #770596

#	Time	Username	Problem	Language	Result	Execution time	Memory
770596		_martynas	Paint By Numbers (IOI16_paint)	C++11	100 / 100	326 ms	7432 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>

using namespace std;

const int mxn = 2e5+5;
const int mxk = 105;

/*
1. Craft a pseudo function that returns a boolean vector for each x "block"
   times each position. [b][i] - true if it's possible to place first b+1 blocks
   and the b-th one ending at i-th position
2. Run this function once
3. Reverse inputs
4. Run this function again and reverse it's results
5. If both endpoints of a block at some position are true then some valid
   covering uses that block there. (Finding possible X characters done)
6. To find optional X places try "skipping" them, i.e. going form b to b+1
   blocks where b-th ends before them and b+1-th starts after them.
*/

int n, k;
bool can_X[mxn], can_skip[mxn];
int pref[mxn];

vector<vector<bool>> calc(string s, vector<int> C) {
    vector<vector<bool>> dp(k, vector<bool>(n));
    for(int b = 0; b < k; b++) {
        bool last_reachable = b == 0;
        for(int i = C[b]-1; i < n; i++) {
            if(i >= C[b] && s[i-C[b]] == 'X') {
                last_reachable = false;
            }
            if(i >= C[b]+1 && s[i-C[b]] != 'X' && (b > 0 && dp[b-1][i-C[b]-1])) {
                last_reachable = true;
            }
            // forgot optimizing with prefix sums
            if(last_reachable && pref[i]-(i-C[b] < 0 ? 0 : pref[i-C[b]]) == 0) {
                dp[b][i] = true;
            }
        }
    }
    return dp;
}

string solve_puzzle(string s, vector<int> C) {
    n = s.size();
    k = C.size();
    pref[0] = s[0] == '_';
    for(int i = 1; i < n; i++) {
        pref[i] = pref[i-1]+(s[i] == '_');
    }
    auto dpL = calc(s, C);
    reverse(s.begin(), s.end());
    reverse(C.begin(), C.end());
    pref[0] = s[0] == '_';
    for(int i = 1; i < n; i++) {
        pref[i] = pref[i-1]+(s[i] == '_');
    }
    auto dpR = calc(s, C);
    reverse(s.begin(), s.end());
    reverse(C.begin(), C.end());
    for(int b = 0; b < k; b++) {
        reverse(dpR[b].begin(), dpR[b].end());
    }
    reverse(dpR.begin(), dpR.end());
    // all possible blocks
    for(int b = 0; b < k; b++) {
        for(int i = C[b]-1, rm = 0; i < n; i++) {
            if(dpL[b][i] && dpR[b][i-C[b]+1]) {
                for(int j = max(rm, i-C[b]+1); j <= i; j++) {
                    can_X[j] = true;
                }
                rm = i;
            }
        }
    }
    // all possible skipped positions
    // don't forget skipping rightmost positions
    // this is O(nk) ... probably
    for(int b = 0, rm_done = 0; b < k; b++) {
        int from = b == 0 ? 0 : n+1;
        for(int i = C[b]-1; i < n; i++) {
            if(i >= C[b] && s[i-C[b]] == 'X') {
                from = n+1;
            }
            if(i >= C[b]+1 && s[i-C[b]] != 'X'
               && (b > 0 && dpL[b-1][i-C[b]-1] && dpR[b-1][i-C[b]-C[b-1]])) {
                from = min(from, i-C[b]);
            }
            if(dpL[b][i] && dpR[b][i-C[b]+1]) {
                for(; from <= i-C[b]; from++) {
                    can_skip[from] = true;
                }
                if(!rm_done && b == k-1) {
                    for(int j = i+1; j < n; j++) {
                        can_skip[j] = true;
                    }
                    rm_done = true;
                }
            }
        }
    }
    string ans(n, '9');
    for(int i = 0; i < n; i++) {
        if(!can_X[i]) {
            ans[i] = '_';
        }
        else if(!can_skip[i]) {
            ans[i] = 'X';
        }
        else {
            ans[i] = '?';
        }
    }
    return ans;
}
/*
.X.X._.X_..
2 3 2

..X.._.X_..
2 3 2

sample:
..........
2
3 4

........
2
3 4

..._._....
1
3

.X........
1
3
*/

• 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