제출 #50976

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
50976		tincamatei	Paint By Numbers (IOI16_paint)	C++14	32 / 100	4 ms	1020 KiB

paint

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

using namespace std;

const int MAX_N = 200000;
const int MAX_K = 100;

bool dp[1+MAX_K][1+MAX_N];
bool sp[1+MAX_K][1+MAX_N];

int white[1+MAX_N];
int black[1+MAX_N];

int pozitii[1+MAX_N], top;
int cuts[1+MAX_N], top2;

string solve_puzzle(string s, vector<int> c) {
  int n = s.size(), k = c.size();
  string result(n, 0);
  s.insert(s.begin(), 0);
  c.insert(c.begin(), 0);

  for (int i = 1; i <= n; ++i) {
    white[i] = white[i - 1] + (s[i] == '_');
    black[i] = black[i - 1] + (s[i] == '*');
  }

  dp[0][0] = sp[0][0] = true;
  for (int i = 1; i <= n; ++i) {
    if(s[i] == 'X')
      dp[0][i] = sp[0][i] = false;
    else {
      dp[0][i] = dp[0][i - 1];
      sp[0][i] = sp[0][i - 1];
    }
  }

  for (int i = 1; i <= k; ++i) {
    for (int j = c[i]; j <= n; ++j) {
      if (white[j] - white[j - c[i]] == 0 && (j - c[i] - (i != 1) >= 0 && s[j - c[i]] != 'X'))
        dp[i][j] = sp[i - 1][j - c[i] - (i != 1)];

      if (s[j] == 'X')
        sp[i][j] = dp[i][j];
      else
        sp[i][j] = sp[i][j - 1] | dp[i][j];
    }
  }

  cuts[top2++] = n;
  for(int i = k; i >= 1; --i) {
    top = 0;

    for(int j = 0; j < top2; ++j) {
      int j2 = cuts[j];

      if(dp[i][j2])
        pozitii[top++] = j2;
      while(s[j2] != 'X' && j2 > cuts[j + 1] + 1) {
        --j2;
        if(dp[i][j2])
          pozitii[top++] = j2;
      }
    }

    int st = 0, dr = 1000000000;
    for(int j = 0; j < top; ++j) {
      st = max(st, pozitii[j] - c[i] + 1);
      dr = min(dr, pozitii[j]);
    }

    for(int j = st; j <= dr; ++j)
      result[j - 1] = 'X';

    for(int j = 0; j < top; ++j) {
      int j2 = pozitii[j];
      while(j2 > pozitii[j + 1] && j2 > pozitii[j] - c[i]) {
        if(result[j2 - 1] != 'X')
          result[j2 - 1] = '?';
        --j2;
      }
    }

    top2 = 0;
    for(int j = 0; j < top; ++j)
      cuts[top2++] = pozitii[j] - c[i] - 1;
  }

  for (int i = 0; i < n; ++i)
    if(result[i] == 0)
      result[i] = '_';
  return result;
}

#ifndef EVAL
const int S_MAX_LEN = 200 * 1000;
char buf[S_MAX_LEN + 1];

int main() {
    assert(1 == scanf("%s", buf));
    std::string s = buf;
    int c_len;
    assert(1 == scanf("%d", &c_len));
    std::vector<int> c(c_len);
    for (int i = 0; i < c_len; i++) {
        assert(1 == scanf("%d", &c[i]));
    }
    std::string ans = solve_puzzle(s, c);

    printf("%s\n", ans.data());
    return 0;
}

#endif

• 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