제출 #571825

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
571825		PiejanVDC	Paint By Numbers (IOI16_paint)	C++17	59 / 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) {
    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 = 0;
  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 = 0;
  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();

  prefW.resize(n+5,0);
  prefX.resize(n+5,0);
  le.resize(n+5,0);
  ri.resize(n+5,-1);
  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);

  rdfs(k-1, n-1);

  for(int i = 0 ; i < k ; i++) {
    if(ri[i] == -1) {
      assert(0);
    }
  }

  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;
}


#include <vector>
#include <string>
#include <cstdio>
#include <cassert>

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