Submission #1198268

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

paint

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

string solve_puzzle(string s, vector<int> c) {
  int n = s.size();
  int k = c.size();
  
  vector<int> pref(n + 1, 0);
  for (int i = 0; i < n; i++) {
    pref[i + 1] = pref[i] + (s[i] == '_');
  }
  
  auto sum = [&](int l, int r) -> int {
    return pref[r + 1] - pref[l];
  };
  
  vector<vector<bool>> dp1(n + 2, vector<bool>(k + 1, false));
  vector<vector<bool>> dp2 = dp1;
  
  dp1[0][0] = true;
  for (int i = 0; i <= n; i++) {
    for (int j = 0; j <= k; j++) {
      if (i != n && s[i] == 'X') continue;
      
      if (dp1[i][j]) dp1[i + 1][j] = true;
      else if (j > 0) {
        int cnt = c[j - 1];
        if (i < cnt) continue;
        if (sum(i - cnt, i - 1)) continue;
        if (dp1[i - cnt][j - 1]) dp1[i + 1][j] = true;
      }
    }
  }
  
  dp2[n][0] = true;
  for (int i = n - 1; i >= 0; i--) {
    for (int j = 0; j <= k; j++) {
      if (s[i] == 'X') continue;
      
      if (dp2[i + 1][j]) dp2[i][j] = true;
      else if (j > 0) {
        int cnt = c[k - j];
        if (n - i - 1 < cnt) continue;
        if (sum(i + 1, i + cnt)) continue;
        if (dp2[i + cnt + 1][j - 1]) dp2[i][j] = true;
      }
    }
  }
  
  vector<bool> white(n + 1, false);
  vector<int> diff(n + 1, 0);
  for (int i = 0; i <= n; i++) {
    if (i != n && s[i] != '.') continue;
    for (int j = 0; j <= k; j++) {
      if (!dp1[i + 1][j] || !dp2[i][k - j]) continue;
      
      white[i] = true;
      if (j == 0) continue;
      int cnt = c[j - 1];
      if (i >= cnt && sum(i - cnt, i - 1) == 0) {
        diff[i - cnt]++;
        diff[i]--;
      }
    }
  }
  for (int i = 1; i <= n; i++) diff[i] += diff[i - 1];
  
  string ans = s;
  for (int i = 0; i < n; i++) {
    if (ans[i] != '.') continue;
    
    // assert(diff[i] || white[i]);
    if (diff[i] && white[i]) ans[i] = '?';
    else if (diff[i]) ans[i] = 'X';
    else ans[i] = '_';
  }
  
  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: 3 / 3
• Subtask 3: 22 / 22
• Subtask 4: 0 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10