QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#761379#6602. Journey to Un'GorofosovWA 0ms3572kbC++141.4kb2024-11-18 22:28:562024-11-18 22:29:02

Judging History

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

  • [2024-11-18 22:29:02]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3572kb
  • [2024-11-18 22:28:56]
  • 提交

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';
}


Details

Tip: Click on the bar to expand more detailed information

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'