Submission #572129

#	Time	Username	Problem	Language	Result	Execution time	Memory
572129		PiejanVDC	Paint By Numbers (IOI16_paint)	C++17	10 / 100	2051 ms	2004 KiB

paint

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

vector<int>v;
string s;

const int mxN = (int)2e5 + 5;
const int mxK = (int)1e2 + 5;

int dp[mxK][mxN];
int rdp[mxK][mxN];

vector<int>prefW,prefX;

int n,k;

bool dfs(int i, int x) {
  if(i == k) {
    if(prefX[min(x+1,n)] == prefX[min(n,x)])
      return 1;
    return 0;
  }
  if(x >= n || x + v[i] - 1 >= n) {
    return 0;
  }
  if(dp[i][x])
    return dp[i][x];
  if(s[x] == 'X') {
    // last time here
    bool ok = 0;
    if(prefW[x + v[i]] - prefW[x] == 0 && (x + v[i] == n || s[x + v[i]] != 'X')) {
      ok = dfs(i+1, x + v[i] + 1);
    }
    return dp[i][x] = ok;
  }

  bool ok = dfs(i, x+1);
  if(prefW[x + v[i]] - prefW[x] == 0 && (x + v[i] == n || s[x + v[i]] != 'X')) {
    ok |= dfs(i+1, x + v[i] + 1);
  }
  return dp[i][x] = ok;
}

bool rdfs(int i, int x) {
  if(i == -1) {
    if(prefX[max(0, x+1)] == 0)
      return 1;
    return 0;
  }
  if(x < 0 || x - v[i] + 1 <= -1) {
    return 0;
  }
  if(rdp[i][x])
    return rdp[i][x];
  if(s[x] == 'X') {
    bool ok = 0;
    if(prefW[x+1] - prefW[x - v[i] + 1] == 0 && (x - v[i] == -1 || s[x - v[i]] != 'X')) {
      ok = rdfs(i-1, x - v[i] - 1);
    }
    return rdp[i][x] = ok;
  }

  bool ok = rdfs(i, x-1);
  if(prefW[x+1] - prefW[x - v[i] + 1] == 0 && (x - v[i] == -1 || s[x - v[i]] != 'X')) {
    ok |= rdfs(i-1, x - v[i] - 1);
  }
  return rdp[i][x] = ok;
}

string solve_puzzle(string S, vector<int>c) {
  s = S;
  v = c;

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

  prefW.resize(mxN);
  prefX.resize(mxN);

  prefW[0] = prefX[0] = 0;

  for(int i = 0 ; i < n ; i++) {
    prefW[i+1] = prefW[i] + (s[i] == '_' ? 1 : 0);
    prefX[i+1] = prefX[i] + (s[i] == 'X' ? 1 : 0);
  }

  //cout << "check 1";

  dfs(0,0);
  //cout << "check 2";
  rdfs(k-1,n-1);



  string ans = "";

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

    if(s[i] != '.') {
      ans += s[i];
      continue;
    }

    bool canX = 0, canW = 0;

    for(int j = 0 ; j < k ; j++) {
      int sz = v[j];

      for(int ii = max(0,i - sz + 1) ; ii <= min(i,n-sz) ; ii++) {
        // no forced white
        // no X and ends
        if((j+1 == k && rdp[j][i-1]) || (dp[j+1][i+1] && rdp[j][i-1])) {
          canW = 1;
        }
        if((j-1 == -1 && dp[j][i+1]) || (dp[j][i+1] && rdp[j][i-1])) {
          canW = 1;
        }

        if(dp[j][ii] && prefW[ii + sz] == prefW[ii] && (ii == 0 || s[ii-1] != 'X') && (ii+sz == n || s[ii + sz] != 'X') && (j-1 == -1 || rdp[j-1][ii-2]) && (j+1 == k || dp[j+1][ii+sz+1])) {
          canX = 1;
          continue;
        }
      }

    }

    if(canW) {
      if(canX) {
        ans += '?';
      } else {
        ans += '_';
      }
    } else {
      ans += 'X';
    }
  }

  return ans;
}

Compilation message (stderr)

paint.cpp: In function 'bool dfs(int, int)':
paint.cpp:34:21: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   34 |     return dp[i][x] = ok;
      |            ~~~~~~~~~^~~~
paint.cpp:41:19: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   41 |   return dp[i][x] = ok;
      |          ~~~~~~~~~^~~~
paint.cpp: In function 'bool rdfs(int, int)':
paint.cpp:60:22: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   60 |     return rdp[i][x] = ok;
      |            ~~~~~~~~~~^~~~
paint.cpp:67:20: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   67 |   return rdp[i][x] = ok;
      |          ~~~~~~~~~~^~~~

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