제출 #590782

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
590782		Sam_a17	Paint By Numbers (IOI16_paint)	C++14	80 / 100	2087 ms	177228 KiB

paint

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <cstdio>
using namespace std;

#define ll long long
#define ld long double

#define all(x) (x.begin(), x.end())
#define rall(x) (x.rbegin(), x.rend())
#define sz(x) (int)x.size()

const int N = 2e5 + 10, K = 1e2 + 10;
int dp[N][K][2], C[N], n, k;
int dp2[N][K][2];
string curr;

// 1 is if true
// -1 is if undef
// 0 if false

int rec(int st, int ki, int flag) {
  // cout << st << " " << ki << " " << flag << endl;
  if(st == n && ki == k) {
    return 1;
  } else if(st == n) {
    dp[st][ki][flag] = 0;
    return 0;
  }

  if(dp[st][ki][flag] != -1) {
    return dp[st][ki][flag];
  }

  int answ = 0;
  if(ki != k) {
    int lst = st, lstX = -1;
    for(int i = st + 1; i <= n; i++) {
      if(curr[i] != 'X' && lstX == -1) {
        int cur = rec(i, ki, 0);
        if(cur) {
          dp2[i][ki][0]++;
        }
        answ |= cur;
      }

      if(curr[i] == '_') {
        lst = i;
        continue;
      }

      if(curr[i] != '_') {
        // if(st == 1) {
          // cout << i - lst << " " << lstX << endl;
        // }
        if(!flag && i - lst >= C[ki + 1] && (lstX == -1 || lstX > (i - C[ki + 1]))) {
          int curr =  rec(i, ki + 1, 1);
          if(curr) {
            int j = i, cnt = 0;
            while(cnt < C[ki + 1]) {
              dp2[j][ki + 1][1]++;
              j--, cnt++;
            }
          }
          answ |= curr;
        }

        if(flag && i - lst > C[ki + 1] && (lstX == -1 || lstX > (i - C[ki + 1]))) {
          int curr =  rec(i, ki + 1, 1);
          if(curr) {
            int j = i, cnt = 0;
            while(cnt < C[ki + 1]) {
              dp2[j][ki + 1][1]++;
              j--, cnt++;
            }
          }
          answ |= curr;
        }

        if(curr[i] == 'X' && lstX == -1) {
          lstX = i;
        }
      }
    }
  } else {
    for(int i = st + 1; i <= n; i++) {
      if(curr[i] == 'X') {
        dp[st][ki][flag] = 0;
        return dp[st][ki][flag];
      }
      int cur = rec(i, ki, 0);
      if(cur) {
        dp2[i][ki][0]++;
      }
      answ |= cur;
    }
  }

  dp[st][ki][flag] = answ;
  return dp[st][ki][flag];
}

string solve_puzzle(string s, vector<int> c) {
  memset(dp, -1, sizeof(dp));

  n = sz(s);
  curr += ".";
  for(int i = 0; i < n; i++) {
    curr += s[i];
  }

  // cout << curr << endl;

  k = sz(c);
  for(int i = 0; i < k; i++) {
    C[i + 1] = c[i];
  }

  rec(0, 0, 0);

  string answ = "";
  for(int i = 1; i <= n; i++) {
    int cnt1 = 0, cnt2 = 0;
    for(int j = 0; j <= k; j++) {
      if(dp2[i][j][0]) {
        cnt1++;
      }
      if(dp2[i][j][1]) {
        cnt2++;
      }

      if(cnt1 && cnt2) {
        break;
      }
    }

    // if(i == 4) {
      // cout << cnt1 << " " << cnt2 << endl;
    // }

    if(cnt1 && !cnt2) {
      answ += "_";
    } else if(!cnt1 && cnt2) {
      answ += "X";
    } else {
      answ += "?";
    }
  }

  return answ;
}

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