Submission #1237809

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237809		kunzaZa183	Paint By Numbers (IOI16_paint)	C++20	7 / 100	0 ms	328 KiB

paint

#include <bits/stdc++.h>
using namespace std;

string solve_puzzle(string s, vector<int> c) {

  vector<int> qsumb(s.size());

  qsumb[0] = s[0] == '_';
  for (int i = 1; i < s.size(); i++)
    qsumb[i] = qsumb[i - 1] + (s[i] == '_');

  auto qryb = [&](int l, int r) {
    if (l == 0)
      return qsumb[r];
    return qsumb[r] - qsumb[l - 1];
  };

  vector<vector<bool>> vvb(c.size() + 1, vector<bool>(s.size() + 1)),
      suf(c.size() + 1, vector<bool>(s.size() + 1));

  vvb[0][0] = 1;

  for (int i = 0; i < s.size(); i++) {
    if (s[i] == 'X')
      break;
    vvb[0][i + 1] = 1;
  }

  for (int i = 1; i <= c.size(); i++) {
    for (int j = 1; j <= s.size(); j++) {
      if (s[j - 1] != 'X') {
        vvb[i][j] = vvb[i][j] || vvb[i][j - 1];
      }
      if (s[j - 1] != '_') {
        if ((j - c[i - 1] < 0) || (qryb(j - c[i - 1], j - 1) != 0)) {
        } else if (i == 1) {
          vvb[i][j] = 1;
        } else if (j - c[i - 1] - 1 >= 0 && s[j - c[i - 1] - 1] != 'X' &&
                   vvb[i - 1][j - c[i - 1] - 1]) {
          vvb[i][j] = 1;
        }
      }
    }
  }

  suf[c.size()][s.size()] = 1;

  for (int i = s.size() - 1; i >= 0; i--) {
    if (s[i] == 'X')
      break;
    suf[c.size()][i] = 1;
  }

  for (int i = c.size() - 1; i >= 0; i--) {
    for (int j = s.size() - 1; j >= 0; j--) {
      if (s[j] != 'X') {
        suf[i][j] = suf[i][j] || suf[i][j + 1];
      }
      if (s[j] != '_') {
        if ((j + c[i] - 1 >= s.size()) || (qryb(j, j + c[i] - 1) != 0)) {
        } else if (i == c.size() - 1) {
          suf[i][j] = 1;
        } else if (j + c[i] + 1 <= s.size() && s[j + c[i]] != 'X' &&
                   suf[i + 1][j + c[i] + 1]) {
          suf[i][j] = 1;
        }
      }
    }
  }

  vector<bool> canw(s.size());
  vector<int> canb(s.size() + 1);

  for (int i = 0; i <= c.size(); i++) {
    for (int j = 0; j < s.size(); j++) {
      canw[j] = canw[j] || (vvb[i][j] && suf[i][j+1]);
    }
  }

  for (int i = 0; i < c.size(); i++) {
    for (int j = 0; j < s.size(); j++) {
      bool can = 1;

      if (j != 0)
        can = can && (s[j - 1] != 'X');
      if (j + c[i] < s.size())
        can = can && (s[j + c[i]] != 'X');

      if ((j + c[i] - 1 >= s.size()) || qryb(j, j + c[i] - 1) != 0)
        continue;

      can = can && vvb[i][j] && suf[i + 1][j + c[i]];

      if (can) {
        canb[j]++;
        canb[j + c[i]]--;
      }
    }
  }

  vector<bool> vbb(s.size());
  int cur = 0;
  for (int i = 0; i < s.size(); i++) {
    cur += canb[i];
    if (cur > 0)
      vbb[i] = 1;
  }

  string ans;
  for (int i = 0; i < s.size(); i++)
    if (s[i] != '.')
      ans.push_back(s[i]);
    else {
      if (canw[i] && vbb[i])
        ans.push_back('?');
      else if (canw[i])
        ans.push_back('_');
      else
        ans.push_back('X');
    }

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