Submission #902346

#	Time	Username	Problem	Language	Result	Execution time	Memory
902346		nguyentunglam	Paint By Numbers (IOI16_paint)	C++17	100 / 100	220 ms	47060 KiB

paint

#include<bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#define ii pair<int, int>
using namespace std;

const int N = 2e5 + 10;

bool f[N][110], g[N][110];

int pref[N];

int black[N], white[N];

std::string solve_puzzle(std::string s, std::vector<int> c) {
  int n = s.size();
  s = " " + s;
  int k = c.size();
  c.insert(c.begin(), 0);
  for(int i = 1; i <= n; i++) pref[i] = pref[i - 1] + (s[i] == '_');

  f[0][0] = g[n + 1][k + 1] = 1;

  for(int i = 1; i <= n; i++) {
    for(int j = 0; j <= k; j++) if (s[i] != 'X') f[i][j] = f[i - 1][j];
    for(int j = 1; j <= k; j++) if (c[j] <= i && pref[i] - pref[i - c[j]] == 0) {
      if (i - c[j] == 0) f[i][j] = f[0][j - 1];
      else if (s[i - c[j]] != 'X') f[i][j] |= f[i - c[j] - 1][j - 1];
    }
  }

  for(int i = n; i >= 1; i--) {
    for(int j = 1; j <= k + 1; j++) if (s[i] != 'X') g[i][j] = g[i + 1][j];
    for(int j = 1; j <= k; j++) if (i + c[j] - 1 <= n && pref[i + c[j] - 1] - pref[i - 1] == 0) {
      if (i + c[j] - 1 == n) g[i][j] = g[n + 1][j + 1];
      else if (s[i + c[j]] != 'X') g[i][j] |= g[i + c[j] + 1][j + 1];
    }
  }

  for(int i = 1; i <= n; i++) if (s[i] == '.') for(int j = 0; j <= k; j++) {
    white[i] |= f[i - 1][j] & g[i + 1][j + 1];
  }


  for(int i = 1; i <= n; i++) for(int j = 1; j <= k; j++) if (i >= c[j]) {
    if (pref[i] - pref[i - c[j]]) continue;
    int from = i - c[j], to = i + 1;
    if (from == 0 && j > 1) continue;

    if (from) {
      if (s[from] == 'X') continue;
      from--;
    }
    if (to <= n) {
      if (s[to] == 'X') continue;
      to++;
    }
    if (f[from][j - 1] & g[to][j + 1]) {
      black[i - c[j] + 1]++;
      black[i + 1]--;
    }
  }


  string ret;

  for(int i = 1; i <= n; i++) {
    black[i] += black[i - 1];
    if (s[i] != '.') ret.push_back(s[i]);
    else if (black[i] && white[i]) ret.push_back('?');
    else if (black[i]) ret.push_back('X');
    else ret.push_back('_');
  }

  return ret;
}

#ifdef ngu
int main() {

  freopen ("task.inp", "r", stdin);
  freopen ("task.out", "w", stdout);

  string s; cin >> s;
  int k; cin >> k;
  vector<int> c(k);
  for(int i = 0; i < k; i++) cin >> c[i];
  cout << solve_puzzle(s, c);
}
#endif // ngu

• 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