QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#733324 | #8776. Not Another Constructive! | jiujiu | WA | 71ms | 3860kb | C++20 | 2.0kb | 2024-11-10 18:16:56 | 2024-11-10 18:16:56 |
Judging History
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