Submission #1190554

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190554		JelalTkm	Paint By Numbers (IOI16_paint)	C++17	0 / 100	0 ms	320 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;

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] + (s[i] == '_');
  }

  vector<vector<vector<int>>> dp(n + 1, vector<vector<int>> (k + 1, vector<int> (2)));
  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 + 1), pref1(n + 1);
  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--) {
    
//   }

//   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: 0 / 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