QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#733288#8776. Not Another Constructive!jiujiuWA 0ms3816kbC++202.0kb2024-11-10 18:07:152024-11-10 18:07:18

Judging History

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

  • [2024-11-10 18:07:18]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3816kb
  • [2024-11-10 18:07:15]
  • 提交

answer

#include <bits/stdc++.h>
using ld = long double;
using i64 = long long;

#define NO std::cout << "No\n"
#define YES std::cout << "Yes\n"
#define all(x) x.begin(), x.end()

// std::default_random_engine Rand;
// std::uniform_int_distribution<int> r1(1, 10);
// constexpr int d[4][2] = {-1, 0, 0, 1, 1, 0, 0, -1};

struct BT{
	int n;
	std::vector<int> t;
	BT(int n):n(n){
		t.assign(n + 1, 0);
	}
	void add(int i, int val){
		for(;i <= n; i += (i & (-i))) t[i] += val;
	}
	int ask(int i){
		int res = 0;
		for(;i; i -= (i & (-i))) res += t[i]; 
		return res;
	}
	int ask(int l, int r){
		return ask(r) - ask(l - 1);
	}
};

void solve() {
	int n, k;
	std::cin >> n >> k;
	std::string s;
	std::cin >> s;
	BT N(n + 1), C(n + 1);
	for(int i = 1; i <= n; i++){
		if(s[i - 1] == 'N') N.add(i, 1);
		if(s[i - 1] == 'C') C.add(i, 1);
	}
	int ans = 0;
	for(int i = 1; i <= n; i++){
		if(s[i - 1] == 'A'){
			ans += N.ask(i) * C.ask(i, n);
		}
	}
	if(ans > k){
		std::cout << "-1\n";
		return;
	}
	char op[4] = {'S', 'N', 'A', 'C'};
	int flag = 0;
	auto dfs = [&](auto &&self, int x, int res){
		if(x == n && res == k){
			flag = 1;
			return;
		}
		if(flag)return;
		for(int i = x; i <= n; i++){
			if(s[i - 1] == '?'){
				for(int j = 0; j < 4; j++){
					s[i - 1] = op[j];
					if(j == 1) N.add(i, 1);
					if(j == 3) C.add(i, 1);
					self(self, x + 1, res + (j == 2 ? N.ask(i) + C.ask(i, n) : 0));
					if(flag) return;
					s[i - 1] = '?';
					if(j == 1) N.add(i, -1);
					if(j == 3) C.add(i, -1);
				}
			} else {
				self(self, x + 1, res);
			}
		}
	};
	dfs(dfs, 1, ans);
	if(flag){
		std::cout << s << "\n";
	} else {
		std::cout << "-1\n" << "\n";
	}
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    // Rand.seed(time(0));

    int _ = 1;

    // std::cin >> _;
    // scanf("%ld",&_);
    // std::cout<<std::fixed<<std::setprecision(2);

    while (_--) {
        solve();
    }
    return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3816kb

input:

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

output:

NSSASSSSSSCSSSSSSSSSAS

result:

wrong answer incorrect number of subsequences: 1