Submission #321210

#	Time	Username	Problem	Language	Result	Execution time	Memory
321210		quocnguyen1012	Paint By Numbers (IOI16_paint)	C++14	100 / 100	468 ms	44596 KiB

paint

#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e5 + 5;

bool pref[maxn][105], suf[maxn][105];
int N, K, sum[maxn];
int black[maxn];
bool white[maxn];
string res;

string solve_puzzle(string str, vector<int> req) {
  N = str.size();
  K = req.size();

  for (int i = 1; i <= N; ++i) {
    sum[i] = sum[i - 1] + (str[i - 1] == '_');
  }
  pref[0][0] = true;
  suf[N][K] = true;

  for (int i = 0; i < N; ++i) {
    for (int j = 0; j <= K; ++j) {
      if (str[i] != 'X') {
        pref[i + 1][j] |= pref[i][j];
      }
      if (j < K) {
        if (i + req[j] < N && str[i + req[j]] != 'X' && sum[i + req[j]] == sum[i]) {
          pref[i + req[j] + 1][j + 1] |= pref[i][j];
        }
      }
    }
  }
  for (int i = N; i >= 1; --i) {
    for (int j = 0; j <= K; ++j) {
      if (str[i - 1] != 'X') {
        suf[i - 1][j] |= suf[i][j];
      }
      if (j >= 1) {
        if (i - req[j - 1] > 0 && str[i - req[j - 1] - 1] != 'X' && sum[i - req[j - 1]] == sum[i]) {
          suf[i - req[j - 1] - 1][j - 1] |= suf[i][j];
        }
      }
    }
  }

  for (int i = 0; i < N; ++i) {
    for (int j = 0; j <= K; ++j) {
      white[i] = max(white[i], min(pref[i + 1][j], suf[i][j]));
    }
    for (int j = 0; j < K; ++j) {
      if (i + req[j] <= N && pref[i][j] && suf[i + req[j]][j + 1] && sum[i + req[j]] == sum[i]) {
        ++black[i];
        --black[i + req[j]];
      }
    }

    if (i) black[i] += black[i - 1];
    if (black[i] && white[i]) {
      res += '?';
    } else if (black[i]) {
      res += 'X';
    } else {
      res += '_';
    }
  }
  return res;
}

#ifdef LOCAL
signed main(void) {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifdef LOCAL
  freopen("A.INP", "r", stdin);
  freopen("A.OUT", "w", stdout);
#endif // LOCAL
  string str; cin >> str;
  int k; cin >> k;
  vector<int> c(k);
  for (int & i : c) cin >> i;
  cout << solve_puzzle(str, c);
}
#endif // LOCAL

• 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