Submission #902608

#	Time	Username	Problem	Language	Result	Execution time	Memory
902608		Blagoj	Paint By Numbers (IOI16_paint)	C++17	32 / 100	2 ms	2036 KiB

paint

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

using namespace std;

const int mxn = 2e5 + 10;

int pfxW[mxn], pfxB[mxn];

int getW(int l, int r) {
    return pfxW[r] - pfxW[l - 1];
}

int getB(int l, int n) {
    return pfxB[n - 1] - pfxB[l - 1];
}

string solve(string s, vector<int> c) {
    memset(pfxW, 0, sizeof(pfxW));
    memset(pfxB, 0, sizeof(pfxB));
    s = "." + s;
    int n = s.size(), k = c.size();
    for (int i = 1; i < n; i++) pfxW[i] = pfxW[i - 1] + (s[i] == '_');
    for (int i = 1; i < n; i++) pfxB[i] = pfxB[i - 1] + (s[i] == 'X');
    bool dp[n][k + 1];
    int from[n][k + 1];
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;
    int pos = n;
    for (int i = 1; i < n; i++) {
        if (s[i] != 'X') dp[i][0] = dp[i - 1][0];
        for (int j = 1; j <= k; j++) {
            if (((j == 1 && i - c[j - 1] >= 0) || (j > 1 && i - c[j - 1] - 1 >= 0)) && getW(i - c[j - 1] + 1, i) == 0) {
                if (j < k) {
                    int val = (j == 1 ? dp[i - c[j - 1]][j - 1] : dp[i - c[j - 1] - 1][j - 1]);
                    if (val) {
                        dp[i][j] = 1;
                        from[i][j] = i - c[j - 1] - 1;
                    }
                }
                else if (getB(i + 1, n) == 0) {
                    int val = (j == 1 ? dp[i - c[j - 1]][j - 1] : dp[i - c[j - 1] - 1][j - 1]);
                    if (val) {
                        dp[i][j] = 1;
                        from[i][j] = i - c[j - 1] - 1;
                        pos = min(pos, i);
                    }
                }
            }
        }
    }
    string ans;
    for (int i = 0; i < n; i++) ans += "_";
    int cnt = k;
    while (pos && cnt) {
        if (dp[pos][cnt]) {
            for (int i = pos; i > from[pos][cnt] + 1; i--) ans[i] = 'X';
            pos = from[pos][cnt];
            cnt--;
        }
        else pos--;
    }
    return ans.substr(1);
}

string solve_puzzle(string s, vector<int> c) {
    string l = solve(s, c);
    reverse(s.begin(), s.end());
    reverse(c.begin(), c.end());
    string r = solve(s, c);
    reverse(r.begin(), r.end());
    if (l == r) return l;
    string ans = "";
    for (int i = 0; i < s.size(); i++) ans += "?";
    int cntL = 0, cntR = 0;
    for (int i = 0; i < s.size(); i++) {
        if (l[i] != '_' || r[i] != '_') break;
        ans[i] = '_';
    }
    for (int i = s.size() - 1; i >= 0; i--) {
        if (l[i] != '_' || r[i] != '_') break;
        ans[i] = '_';
    }
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '_') ans[i] = '_';
        if (l[i] == 'X' && r[i] == 'X' && cntL == cntR) ans[i] = 'X';
        if (i && l[i] == '_' && l[i - 1] == 'X') cntL++;
        if (i && r[i] == '_' && r[i - 1] == 'X') cntR++;
    } 
    // cout << l << " " << r << endl;
    return ans;
}

Compilation message (stderr)

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:74:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for (int i = 0; i < s.size(); i++) ans += "?";
      |                     ~~^~~~~~~~~~
paint.cpp:76:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for (int i = 0; i < s.size(); i++) {
      |                     ~~^~~~~~~~~~
paint.cpp:84:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     for (int i = 0; i < s.size(); i++) {
      |                     ~~^~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 3 / 3
• Subtask 3: 22 / 22
• Subtask 4: 0 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10