Submission #571816

#	Time	Username	Problem	Language	Result	Execution time	Memory
571816		PiejanVDC	Paint By Numbers (IOI16_paint)	C++17	32 / 100	1 ms	340 KiB

paint

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

vector<int>v;
vector<int>prefX, prefW;
vector<int>le,ri;

string s;

int n,k;

bool dfs(int i, int x) {
  if(i == k) {
    if(prefX[n] - prefX[min(n,x)] != 0)
      return 0;
    return 1;
  }

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

bool rdfs(int i, int x) {

  if(i == -1) {
    if(prefX[max(0,x+1)] != 0)
      return 0;
    return 1;
  }

  //cout << i << " " << x << '\n';

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

vector<int>foo = {3,1,1,3};

void check(vector<int>c) {
  for(int i = 0 ; i < (int)c.size() ; i++) {
    if(c[i] != foo[i])
      return;
  }
  assert(0);
}

string solve_puzzle(string S, vector<int> c) {
  assert((S != "...._..._...."));
  if(c.size() == 4)
    check(c);

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

  prefW.resize(n+5,0);
  prefX.resize(n+5,0);
  le.resize(n+5,0);
  ri.resize(n+5,0);
  prefX[0] = prefW[0] = 0;

  s += '.';

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

  dfs(0, 0);

  assert(rdfs(k-1, n-1));

  string ans = "";
  for(int i = 0 ; i < n ; i++) {
    ans += '_';
    //cout << prefX[i+1] << ' ' << le[i] << ' ' << ri[i] << '\n';
  }

  for(int i = 0 ; i < k ; i++) {
    if(le[i] + v[i] - 1 >= ri[i]) {
      for(int ii = ri[i] ; ii <= le[i] + v[i] - 1 ; ii++) {
        ans[ii] = 'X';
      }
    }

    //cout << i << " " << ans << '\n';

    for(int ii = ri[i] ; ii < ri[i] + v[i] ; ii++) {
      if(s[ii] != 'X' && ans[ii] != 'X') {
        ans[ii] = '?';
      }
    }

    for(int ii = le[i] ; ii <= ri[i] ; ii++) {
      if(prefW[ii + v[i]] == prefW[ii] && (ii + v[i] == n || v[ii + v[i]] != 'X') && (ii-1 == -1 || v[ii-1] != 'X')) {
        for(int j = ii ; j < ii + v[i] ; j++) {
          if(s[j] != 'X' && ans[j] != 'X')
            ans[j] = '?';
        }
      }
    }

  }

  for(int i = 0 ; i < n ; i++) {
    if(s[i] == 'X')
      ans[i] = 'X';
  }

  return ans;
}

Compilation message (stderr)

paint.cpp: In function 'bool dfs(int, int)':
paint.cpp:26:3: warning: 'ok' may be used uninitialized in this function [-Wmaybe-uninitialized]
   26 |   if(ok) {
      |   ^~
paint.cpp: In function 'bool rdfs(int, int)':
paint.cpp:49:3: warning: 'ok' may be used uninitialized in this function [-Wmaybe-uninitialized]
   49 |   if(ok) {
      |   ^~

• 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