Submission #590811

#	Time	Username	Problem	Language	Result	Execution time	Memory
590811		Sam_a17	Paint By Numbers (IOI16_paint)	C++14	0 / 100	67 ms	172428 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], p[N];
string curr;

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

int rec(int st, int ki, int flag) {
  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(!flag && i - lst >= C[ki + 1] && (lstX == -1 || lstX > (i - C[ki + 1]))) {
          int curr =  rec(i, ki + 1, 1);
          if(curr) {
            int prefStart = i - C[ki + 1] + 1, prefEnd = i + 1;
            dp2[prefStart][ki + 1][1]++;
            dp2[prefEnd][ki + 1][1]--;
          }
          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 prefStart = i - C[ki + 1] + 1, prefEnd = i + 1;
            dp2[prefStart][ki + 1][1]++;
            dp2[prefEnd][ki + 1][1]--;
          }
          answ |= curr;
        }
 
        if(curr[i] == 'X' && lstX == -1) {
          lstX = i;
        }
      }
    }
  } else {
      if(curr[st + 1] == 'X') {
        dp[st][ki][flag] = 0;
        return dp[st][ki][flag];
      }
      int cur = rec(st + 1, ki, 0);
      if(cur) {
        dp2[st + 1][ki][0]++;
      }
  }

  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];
    if(s[i] == '_') {
      p[i + 1] = p[i] + 1;
    }
  }

  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++) {
      dp2[i][j][1] += dp2[i - 1][j][1];
    }

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

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

  return answ;
}

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