Submission #1052495

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052495		cjoa	Paint By Numbers (IOI16_paint)	C++17	80 / 100	2068 ms	1716 KiB

paint

#include "paint.h"

#include <bits/stdc++.h>

using namespace std;

string S;
vector<int> C;

bool can_substring_be_black(int l, int r) {
   if (r >= (int) S.size())
      return false;

   if (l-1 >= 0 and S[l-1] == 'X')
      return false;

   for (int j = l; j <= r; j++) {
      if (S[j] == '_')
         return false;
   }

   if (r+1 < (int) S.size() and S[r+1] == 'X')
      return false;

   return true;
}

const int MAXN = 5000;
const int MAXK = 100;



bool cached[MAXN+1][MAXK+1];
bool memo[MAXN+1][MAXK+1];

// dp(i, k) = true si es posible llenar el substring S[i .. N-1]
//            y que cumpla con las condiciones de C[k], C[k+1], ...
bool dp( int i, int k ) {
   if (i >= (int) S.size()) {
      if (k == (int) C.size())
         return true;
      else
         return false;
   }

   if (cached[i][k])
      return memo[i][k];

   bool res = false;

   if (S[i] == '_') {
      res = dp(i + 1, k);
   }
   else if (S[i] == 'X') {
      // las proximas C[k] celdas deben ser negros
      if (k < (int) C.size()) {
         bool ok = can_substring_be_black(i, i + C[k] - 1);
         if (ok) {
            res = dp( i + C[k] + 1, k+1 );
         }
      }
   }
   else {  // S[i] == '.'
      // intentamos pintar S[i] de negro
      if (k < (int) C.size()) {
         bool ok = can_substring_be_black(i, i + C[k] - 1);
         if (ok) {
            res = dp( i + C[k] + 1, k+1 );
         }
      }
      
      if (!res) {
         // intentamos pintar S[i] de blanco
         res = dp(i + 1, k);
      }
   }

   cached[i][k] = true;
   memo[i][k] = res;

   return res;
}

std::string solve_puzzle(std::string s, std::vector<int> c) {
   S = s;
   C = c;

   string res(s.size(), '?');
   for (int i = 0; i < (int) s.size(); i++) {  // O(N)
      if (s[i] == '.') {
         // forzar s[i] a que sea negro
         S[i] = 'X';
         for (int i = 0; i <= (int) s.size(); i++)
            for (int k = 0; k <= (int) c.size(); k++)
               cached[i][k] = false;
         bool can_be_black = dp( 0, 0 );
         
         // forzar s[i] a que sea blanco
         S[i] = '_';
         for (int i = 0; i <= (int) s.size(); i++)
            for (int k = 0; k <= (int) c.size(); k++)
               cached[i][k] = false;
         bool can_be_white = dp( 0, 0 );

         if (can_be_black and can_be_white)
            res[i] = '?';
         else if (can_be_black)
            res[i] = 'X';
         else if (can_be_white)
            res[i] = '_';
         else  // no debemos llegar a este else
            assert( false );

         S[i] = '.';
      }
      else
         res[i] = s[i];
   }
   return res;
}

• Subtask 1: 7 / 7
• Subtask 2: 3 / 3
• Subtask 3: 22 / 22
• Subtask 4: 27 / 27
• Subtask 5: 21 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10