QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#602085#8776. Not Another Constructive!ucup-team3691RE 0ms0kbC++202.6kb2024-09-30 19:07:032024-09-30 19:07:03

Judging History

你现在查看的是最新测评结果

  • [2024-09-30 19:07:03]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-09-30 19:07:03]
  • 提交

answer

#include <iostream>
#include <bitset>
#include <queue>
#include <stack>
#include <vector>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <cassert>
#include <algorithm>
#include <cmath>
#include <random>
#include <ctime>
#include <cstdlib>
#include <chrono>

using namespace std;

void solve() {
  int n, k;
  cin >> n >> k;

  string s;
  cin >> s;

  vector<vector<vector<bitset<2500>>>> dp(n + 1, (vector<vector<bitset<2500>>> (n + 1, vector<bitset<2500>>(n + 1))));

  int tc = count(s.begin(), s.end(), 'C'); 
  int tf = count(s.begin(), s.end(), '?'); 

  for (int i = tc; i <= tc + tf; ++i) {
    dp[0][0][i] = 1;
  }

  s = " " + s;
  for (int i = 1; i <= n; ++i) {
    bool nac = false;
    if (s[i] == 'C' || s[i] == '?') {
      nac = true;
      for (int nn = 0; nn <= i; ++nn) {
        for (int nc = 0; nc <= n - i; ++nc) {
          dp[i][nn][nc] |= dp[i - 1][nn][nc + 1];
        }
      }
    }

    if (s[i] == 'N' || s[i] == '?') {
      nac = true;
      for (int nn = 0; nn < i; ++nn) {
        for (int nc = 0; nc <= n - i; ++nc) {
          dp[i][nn + 1][nc] |= dp[i - 1][nn][nc];
        }
      }
    }

    if (s[i] == 'A' || s[i] == '?') {
      for (int nn = 0; nn <= i; ++nn) {
        for (int nc = 0; nc <= n - i; ++nc) {
          dp[i][nn][nc] |= dp[i - 1][nn][nc] << (nn * nc);
        }
      }
    }

    if (!nac || s[i] == '?') {
      for (int nn = 0; nn <= i; ++nn) {
        for (int nc = 0; nc <= n - i; ++nc) {
          dp[i][nn][nc] |= dp[i - 1][nn][nc];
        }
      }
    }
  }

  string ans;
  for (int nn = 0; nn <= n; ++nn) {
    if (dp[n][nn][0].test(k)) {
      int i = n;
      int nc = 0;

      while (i > 0) {
        char ch;
        if (s[i] == 'N' || (s[i] == '?' && nn > 0 && dp[i - 1][nn - 1][nc].test(k))) {
          ch = 'N';
          nn -= 1;
        } else if (s[i] == 'C' || (s[i] == '?' && nc + 1 <= n && dp[i - 1][nn][nc + 1].test(k))) {
          ch = 'C';
          nc += 1;
        } else if (s[i] == 'A' || (s[i] == '?' && nn * nc <= k && dp[i - 1][nn][nc].test(k - nn * nc))) {
          ch = 'A';
          k -= nn * nc;
        } else {
          ch = s[i];
          if (s[i] == '?')
            s[i] = 'X';
        }
         
        ans.push_back(ch);
        --i;
      }
      reverse(ans.begin(), ans.end());
      cout << ans << "\n";
      return;
    }
  }


  cout << "-1\n";
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);

  int t = 1;
  while (t--)
    solve();

  return 0;
}

詳細信息

Test #1:

score: 0
Runtime Error

input:

22 2
N??A??????C???????????

output:


result: