Submission #1190557

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190557		JelalTkm	Paint By Numbers (IOI16_paint)	C++17	100 / 100	182 ms	163460 KiB

paint

#include <bits/stdc++.h>
#include "paint.h"
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

using namespace std;

// #define int long long int

const int N = 2e5 + 10;
const int md = 1e9 + 7;
const int INF = 1e9;

int dp[N][102][2];

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

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

  if (dp[n][k][0] == 1) dp[n][k][0] = 2;
  if (dp[n][k][1] == 1) dp[n][k][1] = 2;
  vector<int> pref0(n + 2), pref1(n + 2);
  for (int i = n; i >= 1; i--) {
    for (int j = 0; j <= k; j++) {
      if (dp[i][j][0] != 2) continue;
      pref0[i] = 1;
      if (dp[i - 1][j][0] == 1) dp[i - 1][j][0] = 2;
      if(dp[i - 1][j][1] == 1) dp[i - 1][j][1] = 2;
    }
    for (int j = 1; j <= k; j++) {
      if (dp[i][j][1] != 2) continue;
      pref1[i + 1] -= 1;pref1[i - c[j - 1] + 1] += 1;
      if(dp[i - c[j - 1]][j - 1][0] == 1) dp[i - c[j - 1]][j - 1][0] = 2;
    }
  }

  string ans = "";
  for (int i = 1; i <= n; i++) {
    pref1[i] += pref1[i - 1];
    if (pref0[i] && pref1[i])
      ans += "?";
    else ans += (pref0[i] ? "_" : "X");
  }

  return ans;
}

// int32_t main(int32_t argc, char *argv[]) {
//   ios::sync_with_stdio(false);
//   cin.tie(nullptr);

//   int T = 1;
//   // cin >> T;
//   while (T--) {
//     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) << '\n';
//   }

//   return 0;
// }

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