QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#733324#8776. Not Another Constructive!jiujiuWA 71ms3860kbC++202.0kb2024-11-10 18:16:562024-11-10 18:16:56

Judging History

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

  • [2024-11-10 18:16:56]
  • 评测
  • 测评结果:WA
  • 用时:71ms
  • 内存:3860kb
  • [2024-11-10 18:16:56]
  • 提交

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 + 1 ){
			if(res == k) flag = 1;
			return;
		}
		if(flag)return;
		if(s[x - 1] == '?'){
			for(int j = 0; j < 4; j++){
				s[x - 1] = op[j];
				if(j == 1) N.add(x, 1);
				if(j == 3) C.add(x, 1);
				self(self, x + 1, res + (j == 2 ? N.ask(x) * C.ask(x, n) : 0));
				if(flag) return;
				s[x - 1] = '?';
				if(j == 1) N.add(x, -1);
				if(j == 3) C.add(x, -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: 100
Accepted
time: 71ms
memory: 3556kb

input:

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

output:

NSSASSSSSACSSSSSSSSSSS

result:

ok correct

Test #2:

score: 0
Accepted
time: 0ms
memory: 3592kb

input:

18 0
COUNTINGSATELLITES

output:

COUNTINGSATELLITES

result:

ok correct

Test #3:

score: 0
Accepted
time: 0ms
memory: 3860kb

input:

2 1
??

output:

-1


result:

ok correct

Test #4:

score: 0
Accepted
time: 0ms
memory: 3780kb

input:

1 0
?

output:

S

result:

ok correct

Test #5:

score: 0
Accepted
time: 0ms
memory: 3612kb

input:

1 0
N

output:

N

result:

ok correct

Test #6:

score: 0
Accepted
time: 0ms
memory: 3552kb

input:

1 0
X

output:

X

result:

ok correct

Test #7:

score: 0
Accepted
time: 0ms
memory: 3556kb

input:

1 1
?

output:

-1


result:

ok correct

Test #8:

score: 0
Accepted
time: 0ms
memory: 3552kb

input:

1 1
N

output:

-1


result:

ok correct

Test #9:

score: 0
Accepted
time: 0ms
memory: 3552kb

input:

1 1
X

output:

-1


result:

ok correct

Test #10:

score: 0
Accepted
time: 0ms
memory: 3552kb

input:

2 0
??

output:

SS

result:

ok correct

Test #11:

score: 0
Accepted
time: 1ms
memory: 3560kb

input:

2 0
N?

output:

NS

result:

ok correct

Test #12:

score: 0
Accepted
time: 0ms
memory: 3616kb

input:

2 0
?C

output:

SC

result:

ok correct

Test #13:

score: 0
Accepted
time: 0ms
memory: 3560kb

input:

2 1
N?

output:

-1


result:

ok correct

Test #14:

score: 0
Accepted
time: 0ms
memory: 3620kb

input:

2 1
?C

output:

-1


result:

ok correct

Test #15:

score: -100
Wrong Answer
time: 0ms
memory: 3588kb

input:

3 1
???

output:

-1


result:

wrong answer returned false