Submission #1059255

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059255		TAhmed33	Paint By Numbers (IOI16_paint)	C++98	100 / 100	1521 ms	244672 KiB

paint

#include "paint.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
 
using namespace std;
 
string solve_puzzle (string s, vector <int> c) {
 
    int n = s.length(), k = c.size();
    c.insert(c.begin(), 0);
    c.push_back(0);
    vector <vector <int>> p(2, vector <int> (n + 2, 0));
    vector <vector <int>> h(2, vector <int> (n + 2, 0));
    vector <vector <int>> f(k + 2, vector <int> (n + 2, 0));
    vector <vector <int>> g(k + 2, vector <int> (n + 3, 0));
    vector <vector <int>> good(k + 2, vector <int> (n + 3, 0));
 
    for (int i = 0; i < n; i++) {
        if (s[i] == '_') p[0][i + 1]++;
        if (s[i] == 'X') p[1][i + 1]++;
    }
 
    for (int i = 1; i <= n + 1; i++) {
        p[0][i] += p[0][i - 1];
        p[1][i] += p[1][i - 1];
    }
 
    f[0][0] = 1;
 
    for (int i = 1; i <= k; i++) {
        for (int j = 1; j <= n + 1; j++) {
            f[i - 1][j] += f[i - 1][j - 1];
        }
        for (int j = c[i]; j <= n; j++) {  
            if (p[0][j] - p[0][j - c[i]] != 0) {
                continue;
            }
            if (j - c[i] == 0) {
                f[i][j] |= f[i - 1][0] != 0;
                continue;
            }
            int L = 1, R = j - c[i], ans = -1;
            while (L <= R) {
                int mid = (L + R) / 2;
                if (p[1][j - c[i]] - p[1][mid - 1] == 0) {
                    R = mid - 1; ans = mid;
                } else {
                    L = mid + 1;
                }
            }
            if (ans == -1) {
                continue;
            }
            f[i][j] = (f[i - 1][j - c[i] - 1] - (ans <= 1 ? 0 : f[i - 1][ans - 2])) != 0;
        }
    }    
    for (int j = 1; j <= n + 1; j++) {
        f[k][j] += f[k][j - 1];
    }
    g[k + 1][n + 1] = 1;
    for (int i = k; i >= 1; i--) {
        for (int j = n; j >= 1; j--) {
            g[i + 1][j] += g[i + 1][j + 1];
        }
        for (int j = n - c[i] + 1; j >= 1; j--) {
            if (p[0][j + c[i] - 1] - p[0][j - 1] != 0) {
                continue;
            }
            if (j + c[i] == n + 1) {
                g[i][j] |= g[i + 1][n + 1];
                continue;
            }
            int L = j + c[i], R = n, ans = -1;
            while (L <= R) {
                int mid = (L + R) / 2;
                if (p[1][mid] - p[1][j + c[i] - 1] == 0) {
                    L = mid + 1; ans = mid;
                } else {
                    R = mid - 1;
                }
            }
            if (ans == -1) {
                continue;
            }
            g[i][j] = (g[i + 1][j + c[i] + 1] - (ans >= n ? 0 : g[i + 1][ans + 2])) != 0;
        }
    }
    for (int i = n; i >= 1; i--) {
        g[1][i] += g[1][i + 1];
    }
    for (int l = 0; l <= k; l++) {
        for (int i = 0; i <= n; i++) {
            if ((f[l][i] - (i == 0 ? 0 : f[l][i - 1])) == 0) {
                continue;
            }
            int L = i + 2, R = n + 1, ans = -1;
            while (L <= R) {
                int mid = (L + R) / 2;
                if (p[1][mid - 1] - p[1][i] == 0) {
                    L = mid + 1; ans = mid;
                } else {
                    R = mid - 1;
                }
            }
            if (ans == -1) {
                continue;
            }
            if (g[l + 1][i + 2] - g[l + 1][ans + 1] == 0) {
                continue;
            }
            h[1][i - c[l] + 1]++; h[1][i + 1]--;
            L = i + 2, R = ans; int ans2 = -1;
            while (L <= R) {
                int mid = (L + R) / 2;
                if (g[l + 1][mid] - g[l + 1][ans + 1]) {
                    L = mid + 1; ans2 = mid;
                } else {
                    R = mid - 1;
                }
            }
            h[0][i + 1]++; h[0][ans2]--;
            good[l + 1][i + 2]++; good[l + 1][ans2 + 1]--;
/*            for (int j = i + 2; j <= ans; j++) {
                if (g[l + 1][j] - g[l + 1][j + 1]) {
                    h[0][i + 1]++; h[0][j]--;
                    h[1][i - c[l] + 1]++; h[1][i + 1]--;
                    h[1][j]++; h[1][j + c[l + 1]]--;
                }
            }*/
        }
    }
    for (int i = 1; i <= k; i++) {
        for (int j = 1; j <= n + 1; j++) {
            good[i][j] += good[i][j - 1];
            if (g[i][j] - g[i][j + 1] && good[i][j]) {
                h[1][j]++; h[1][j + c[i]]--;
            }
        }
    }
    for (int i = 1; i <= n + 1; i++) {
        h[0][i] += h[0][i - 1];
        h[1][i] += h[1][i - 1];
    }
    string ans;
    for (int i = 1; i <= n; i++) {
        if (h[0][i] && h[1][i]) {
            ans.push_back('?');
        } else if (h[0][i]) {
            ans.push_back('_');
        } else {
            ans.push_back('X');
        }
    }
    return ans;
}

• 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