Submission #705975

#	Time	Username	Problem	Language	Result	Execution time	Memory
705975		lukameladze	Paint By Numbers (IOI16_paint)	C++14	100 / 100	269 ms	169104 KiB

paint

#include "paint.h"
# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pb push_back
#define pii pair <int, int>
// dpl[i][j] = 1 ----> prefix{1...i};  s[i] == '_' && c[1] .... c[j] blocks
// dpr[i][j] = 1 ----> suf({i + 1, n});  s[i] == '_' && c[j] ... c[k] blocks
const int N = 2e5 + 5;
int pr_s[N], dpl[N][105],dpr[N][105],lstt[N],prt[N],ans[N]; 
void upd(int le, int ri) {
    pr_s[le]++; pr_s[ri + 1]--;
}
int gett(int le, int ri) {
    return prt[ri] - prt[le - 1];   
}
std::string solve_puzzle(std::string s, std::vector<int> c) {
    s = "@" + s;
    // c . push_front(0) 
    reverse(c.begin(),c.end()); c.pb(0); reverse(c.begin(),c.end());
    int n = (int)s.size() - 1;
    int k = (int)c.size() - 1;
    dpl[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        lstt[i] = lstt[i - 1]; if (s[i] == '_') lstt[i] = i;
        prt[i] = prt[i - 1] + (s[i] == '_');
    }
    dpl[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= k; j++) {
            if (s[i] == 'X') {
                dpl[i][j] = 0; continue;
            }
            dpl[i][j] |= dpl[i - 1][j];
            if (j && (i - 1 - c[j] + 1) >= 1 && gett(i - 1 - c[j] + 1, i - 1) == 0 && dpl[i - 1 - c[j]][j - 1]) {
                dpl[i][j] |= dpl[i - 1 - c[j]][j - 1];
            }
            // (i - 1 - c[j] + 1)  --- (i - 1)
        }
    }
    
    dpr[n + 1][k + 1] = 1;
    for (int i = n; i >= 1; i--) {
        for (int j = k + 1; j >= 1; j--) {
            if (s[i] == 'X') {
                dpr[i][j] = 0; continue;
            }
            dpr[i][j] |= dpr[i + 1][j];
            if (j && (i + 1 + c[j] - 1 <= n) && gett(i + 1, i + 1 + c[j] - 1) == 0) {
                dpr[i][j] |= dpr[i + 1 + c[j]][j + 1];
            }
        }
    }
    
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= k; j++) {
            if (dpl[i][j] && dpr[i][j + 1]) {
                ans[i] = 1;
            } 
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            int le = i - c[j] + 1; int ri = i;
            if (le <= 0) continue;
            if (gett(le, ri) == 0 && dpl[le - 1][j - 1] && dpr[ri + 1][j + 1]) {
                pr_s[le]++; pr_s[ri + 1]--;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        pr_s[i] += pr_s[i - 1];
        if (pr_s[i]) ans[i] += 2;
    }
    string res = "";
    for (int i = 1; i <= n; i++) {
        if (ans[i] == 3) res += "?";
        else if (ans[i] == 1) res += "_";
        else res += "X";
    }
    return res;
}

• 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