Submission #835807

#	Time	Username	Problem	Language	Result	Execution time	Memory
835807		erdemkiraz	Paint By Numbers (IOI16_paint)	C++17	100 / 100	1514 ms	184060 KiB

paint

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

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

const int N = 2e5 + 5;
const int K = 100 + 5;

int n, k;
string s;
vector<int> c;

string ans;

int event[N];
int preW[N], preB[N];
int dpL[N][K], dpR[N][K];

int fL(int x, int i) {
  if(x <= 0) {
    return !i;
  }

  if(!i) {
    return preB[x] == 0;
  }

  if(x < c[i]) {
    return 0;
  }

  int &r = dpL[x][i];
  if(r != -1) {
    return r;
  }

  r = 0;

  if(s[x] != 'X') {
    r |= fL(x - 1, i);
  }

  if(preW[x] - preW[x - c[i]] == 0 and (x - c[i] == 0 or s[x - c[i]] != 'X')) {
    r |= fL(x - c[i] - 1, i - 1);
  }

  return r;
}

int fR(int x, int i) {
  if(x > n) {
    return i == k + 1;
  }

  if(i > k) {
    return preB[n] - preB[x - 1] == 0;
  }

  if(x + c[i] - 1 > n) {
    return 0;
  }

  // if(x == 8 and i == 2) {
  //   printf("c[%d] = %d n = %d\n", i, c[i], n);
  //   puts("ASD");
  // }

  int &r = dpR[x][i];
  if(r != -1) {
    return r;
  }

  r = 0;

  if(s[x] != 'X') {
    r |= fR(x + 1, i);
  }

  if(preW[x + c[i] - 1] - preW[x - 1] == 0 and (x + c[i] == n + 1 or s[x + c[i]] != 'X')) {
    r |= fR(x + c[i] + 1, i + 1);
  }

  return r;
}

void solve() {
  memset(dpL, -1, sizeof dpL);
  memset(dpR, -1, sizeof dpR);

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

  s = "#" + s;
  c.insert(c.begin(), 0);

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

  ans = string(n + 1, '?');

  // for(int i = 1; i <= n; i++) {
  //   for(int j = 1; j <= k; j++) {
  //     printf("fL(%d, %d) = %d fR(%d, %d) = %d\n", i, j, fL(i, j), i, j, fR(i, j));
  //   }
  // }

  for(int i = 1; i <= n; i++) {
    if(s[i] != '.') {
      ans[i] = s[i];
      continue;
    }

    bool flag = false;

    for(int j = 0; j <= k; j++) {
      if(fL(i - 1, j) and fR(i + 1, j + 1)) {
        // printf("i = %d j = %d\n", i, j);
        flag = true;
        break;
      }
    }

    if(!flag) {
      // printf("assign x to %d\n", i);
      ans[i] = 'X';
    }
  }

  // puts(ans.substr(1).c_str());

  for(int j = 1; j <= k; j++) {
    for(int i = 1; i + c[j] - 1 <= n; i++) {
      if(preW[i + c[j] - 1] - preW[i - 1] == 0 and (i + c[j] == n + 1 or s[i + c[j]] != 'X') and (i == 1 or s[i - 1] != 'X')) {
        if(fL(i - 2, j - 1) and fR(i + c[j] + 1, j + 1)) {
          // printf("with %d [%d, %d] could be done\n", j, i, i + c[j] - 1);
          event[i]++;
          event[i + c[j]]--;
        }
      }
    }
  }

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

    // printf("event[%d] = %d\n", i, event[i]);

    if(ans[i] == '?') {
      if(event[i] > 0) {
        ans[i] = '?';
      } else {
        ans[i] = '_';
      }
    }
  }
}

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

  ans = ans.substr(1);

  return ans;
}

• 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