QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#761379 | #6602. Journey to Un'Goro | fosov | WA | 0ms | 3572kb | C++14 | 1.4kb | 2024-11-18 22:28:56 | 2024-11-18 22:29:02 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define lll __int128
#define INF 0x3f3f3f3f
#define LNF 0x3f3f3f3f3f3f3f3fll
#define MOD 998244353
#define pii pair<int, int>
#define pdd pair<double, double>
#define N 100010
int n, tot;
string res[110], cur;
bool valid(string x) {
vector<int> pre(n+1, 0);
for (int i = 1; i <= n; ++ i) pre[i] = (pre[i-1] + (x[i-1] == 'r')) % 2;
int c0 = 0, c1 = 0;
for (int i = 0; i <= n; ++ i) {
c0 += pre[i] == 0;
c1 += pre[i] == 1;
}
if (n%2 == 0) return c0 == c1 + 1 || c1 == c0 + 1;
if (n%2 == 1) return c0 == c1;
return 0;
}
void dfs(int idx, int cp0, int cp1, int cp) {
if (tot == 100) return;
if (cp1 - (cp0 + n - idx) > 1) return;
if (cp0 - (cp1 + n - idx) > 1) return;
if (idx == n && abs(cp0 - cp1) != ((n&1)^1)) return;
if (idx == n) {
assert(valid(cur));
res[tot ++] = cur; return;
}
cur[idx] = 'b';
dfs(idx+1, cp0+(cp==0), cp1+(cp==1), cp);
cur[idx] = 'r';
dfs(idx+1, cp0+(cp==1), cp1+(cp==0), cp^1);
}
int main() {
#ifdef TEST
freopen("zz.in", "r+", stdin);
#endif
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
cur = string(n, '0');
tot = 0;
dfs(0, 1, 0, 0);
cout << tot << '\n';
for (int i = 0; i < tot; ++ i) cout << res[i] << '\n';
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3572kb
input:
1
output:
1 r
result:
ok 2 tokens
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 3568kb
input:
2
output:
3 br rb rr
result:
wrong answer 1st words differ - expected: '2', found: '3'