Submission #1247540

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247540		julia_08	Paint By Numbers (IOI16_paint)	C++20	100 / 100	275 ms	176772 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e5 + 10;
const int MAXK = 110;

int dp_pref[MAXN][MAXK], dp_suf[MAXN][MAXK];

int sum_b[MAXN], sum_w[MAXN];

int white[MAXN], black[MAXN];

string solve_puzzle(string s, vector<int> c){

  int n = s.size();
  int k = c.size();

  s = " " + s;

  for(int i=1; i<=n; i++){
    sum_b[i] = sum_b[i - 1] + (s[i] == 'X');
    sum_w[i] = sum_w[i - 1] + (s[i] == '_');
  }

  dp_pref[0][0] = 1;

  for(int i=1; i<=n; i++){
    for(int j=0; j<=k; j++){

      // black
      if(j > 0){

        if(i == c[j - 1]){
          dp_pref[i][j] |= (dp_pref[i - c[j - 1]][j - 1] && (sum_w[i] - sum_w[i - c[j - 1]] == 0));
        }

        if(i > c[j - 1]){
          dp_pref[i][j] |= (dp_pref[i - c[j - 1] - 1][j - 1] && (sum_w[i] - sum_w[i - c[j - 1]] == 0) && s[i - c[j - 1]] != 'X');
        }

      }

      // white
      if(s[i] != 'X') dp_pref[i][j] |= dp_pref[i - 1][j];

    }
  }

  dp_suf[n + 1][0] = 1;

  for(int i=n; i>=1; i--){
    for(int j=0; j<=k; j++){

      // black
      if(j > 0){

        if(i + c[k - j] - 1 == n){
          dp_suf[i][j] |= (dp_suf[i + c[k - j]][j - 1] && (sum_w[i + c[k - j] - 1] - sum_w[i - 1] == 0));
        }

        if(i + c[k - j] - 1 < n){
          dp_suf[i][j] |= (dp_suf[i + c[k - j] + 1][j - 1] && (sum_w[i + c[k - j] - 1] - sum_w[i - 1] == 0) && s[i + c[k - j]] != 'X');
        }

      }

      // white
      if(s[i] != 'X') dp_suf[i][j] |= dp_suf[i + 1][j];

    }
  }

  for(int i=1; i<=n; i++){
    for(int j=0; j<=k; j++){

      // black
      if(j > 0){

        bool can_pref = false;
        bool can_suf = false;

        if(i == c[j - 1]){
          can_pref = (dp_pref[0][j - 1] && (sum_w[i] - sum_w[i - c[j - 1]] == 0));
        } else if(i > c[j - 1]){
          can_pref = (dp_pref[i - c[j - 1] - 1][j - 1] && (s[i - c[j - 1]] != 'X') && (sum_w[i] - sum_w[i - c[j - 1]] == 0));
        }

        if(i < n - 1){
          can_suf = (dp_suf[i + 2][k - j] && (s[i + 1] != 'X')); 
        } else if(i == n - 1){
          can_suf = ((j == k) && (s[i + 1] != 'X'));
        } else if(i == n) can_suf = (j == k);

        if(can_pref && can_suf){
          black[i - c[j - 1] + 1] ++;
          black[i + 1] --;
        }

      }

      // white
      if(s[i] != 'X') white[i] |= (dp_pref[i - 1][j] && dp_suf[i + 1][k - j]);

    }
  }

  for(int i=1; i<=n; i++) black[i] += black[i - 1];

  string ans;

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

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