Submission #571777

#	Time	Username	Problem	Language	Result	Execution time	Memory
571777		PiejanVDC	Paint By Numbers (IOI16_paint)	C++17	32 / 100	1 ms	308 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)
    return 1;
  if(x >= n || x + v[i] > n)
    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)
    return 1;
  if(x < 0 || x - v[i] < -1)
    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);
}

string solve_puzzle(string S, vector<int> c) {
  v = c;
  s = S;
  n = (int)s.length();
  k = (int)c.size();

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

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

  dfs(0, 0);

  rdfs(k-1, n-1);

  for(int i = 0 ; i < k ; i++) {
    //cout << le[i] << " " << ri[i] << '\n';
  }

  string ans = "";
  for(int i = 0 ; i < n ; i++) {
    ans += '_';
  }

  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] && v[ii + v[i]] != 'X' && 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:22:3: warning: 'ok' may be used uninitialized in this function [-Wmaybe-uninitialized]
   22 |   if(ok) {
      |   ^~
paint.cpp: In function 'bool rdfs(int, int)':
paint.cpp:38:3: warning: 'ok' may be used uninitialized in this function [-Wmaybe-uninitialized]
   38 |   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