QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#769902#6602. Journey to Un'Gorodaylight-et-al#WA 2ms4320kbC++205.7kb2024-11-21 19:49:272024-11-21 19:49:30

Judging History

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

  • [2024-11-21 19:49:30]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:4320kb
  • [2024-11-21 19:49:27]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
template <class T>
using vc = vector<T>;
template <class T>
using vvc = vc<vc<T>>;
template <class T>
using vvvc = vc<vvc<T>>;
#define overload5(a, b, c, d, e, name, ...) name
#define overload4(a, b, c, d, name, ...) name
#define overload3(a, b, c, name, ...) name
#define rep1(n) for (ll i = 0; i < n; ++i)
#define rep2(i, n) for (ll i = 0; i < n; ++i)
#define rep3(i, a, b) for (ll i = a; i < b; ++i)
#define rep4(i, a, b, c) for (ll i = a; i < b; i += c)
#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep1(n) for (ll i = n; i--;)
#define rrep2(i, n) for (ll i = n; i--;)
#define rrep3(i, a, b) for (ll i = b; i-- > (a);)
#define rrep(...) \
    overload4(__VA_ARGS__, rrep4, rrep3, rrep2, rrep1)(__VA_ARGS__)
#define each1(i, a) for (auto &&i : a)
#define each2(x, y, a) for (auto &&[x, y] : a)
#define each3(x, y, z, a) for (auto &&[x, y, z] : a)
#define each4(w, x, y, z, a) for (auto &&[w, x, y, z] : a)
#define each(...) \
    overload5(__VA_ARGS__, each4, each3, each2, each1)(__VA_ARGS__)
#define all1(i) begin(i), end(i)
#define all2(i, a) begin(i), begin(i) + a
#define all3(i, a, b) begin(i) + a, begin(i) + b
#define all(...) overload3(__VA_ARGS__, all3, all2, all1)(__VA_ARGS__)
#define rall1(i) rbegin(i), rend(i)
#define rall2(i, a) rbegin(i), rbegin(i) + a
#define rall3(i, a, b) rbegin(i) + a, rbegin(i) + b
#define rall(...) overload3(__VA_ARGS__, rall3, rall2, rall1)(__VA_ARGS__)
template <class T>
bool chmin(T &a, const T &b) {
    if (a <= b) return 0;
    a = b;
    return 1;
}
template <class T>
bool chmax(T &a, const T &b) {
    if (a >= b) return 0;
    a = b;
    return 1;
}
template <class T, class U>
bool chmin(T &a, const U &b) {
    return chmin(a, (T)b);
}
template <class T, class U>
bool chmax(T &a, const U &b) {
    return chmax(a, (T)b);
}
void solve();
int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    ll t = 1;
    // cin >> t;
    for (int i = 1; i <= t; i++) solve();
    return 0;
}
ll dy[] = {0, 0, 1, 0, -1}, dx[] = {0, 1, 0, -1, 0};
// ll dy[8] = {1, 1, 0, -1, -1, -1, 0, 1}, dx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
void solve() {
    vc<ll> ma = {0};
    rep(i, 1, 1e5 + 10) ma.push_back(ma.back() + (i + 1) / 2);
    ll n;
    cin >> n;
    if (n == 1) {
        cout << 1 << endl << "r" << endl;
        return;
    }
    auto calc = [&](string s) {
        ll res = 0;
        ll cur = 0;
        ll ec = 0, oc = 0;
        for (auto c : s) {
            if (cur == 0)
                ec++;
            else
                oc++;
            if (c == '0') {
                if (cur == 0)
                    res += oc;
                else
                    res += ec;
            } else {
                cur ^= 1;
                if (cur == 0)
                    res += oc;
                else
                    res += ec;
            }
        }
        return res;
    };
    if (n >= 300) {
        ll _n = n - n % 2;
        vc<string> res;
        string s = string(_n, '0');
        s[_n / 2] = '1';
        res.push_back(s);
        s[_n / 2] = '0', s[_n / 2 - 1] = '1';
        res.push_back(s);
        s[_n - 1] = '1';
        res.push_back(s);
        s[_n - 2] = '1';
        res.push_back(s);
        for (int i = _n - 3; i >= _n / 2; i--) {
            s[i] = '1', s[i + 2] = '0';
            res.push_back(s);
            if (res.size() == 100) break;
        }
        if (n % 2 == 1) {
            for (auto &x : res) {
                string x0 = x, x1 = x;
                x0.push_back('0');
                x1.push_back('1');
                if (calc(x0) > calc(x1))
                    x.push_back('0');
                else
                    x.push_back('1');
            }
        }
        cout << ma[n] << endl;
        for (auto x : res) {
            for (auto c : x) cout << (c == '0' ? 'b' : 'r');
            cout << endl;
        }
    } else {
        ll _n = n - n % 2;
        vc<string> res;
        if (_n <= 12) {
            rep(i, 0, 1 << _n) {
                string s;
                rep(j, 0, _n) s.push_back((i >> j & 1) + '0');
                if (calc(s) == ma[_n]) res.push_back(s);
            }
            sort(all(res));
            res.erase(unique(all(res)), res.end());
            while (res.size() > 100) res.pop_back();
        }
        for (int i = 14; i <= _n; i += 2) {
            vc<string> nres;
            for (auto x : res) {
                rep(j, 4) {
                    string tmp = "00";
                    if (j == 1) tmp = "01";
                    if (j == 2) tmp = "10";
                    if (j == 3) tmp = "11";
                    string nx = x + tmp;
                    if (calc(nx) == ma[i]) nres.push_back(nx);
                    nx = tmp + x;
                    if (calc(nx) == ma[i]) nres.push_back(nx);
                }
            }
            sort(all(nres));
            nres.erase(unique(all(nres)), nres.end());
            while (nres.size() > 100) nres.pop_back();
            res = nres;
        }
        if (n % 2 == 1) {
            for (auto &x : res) {
                string x0 = x, x1 = x;
                x0.push_back('0');
                x1.push_back('1');
                if (calc(x0) > calc(x1))
                    x.push_back('0');
                else
                    x.push_back('1');
            }
        }
        cout << ma[n] << endl;
        for (auto x : res) {
            for (auto c : x) cout << (c == '0' ? 'b' : 'r');
            cout << endl;
        }
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 4072kb

input:

1

output:

1
r

result:

ok 2 tokens

Test #2:

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

input:

2

output:

2
br
rb
rr

result:

ok 4 tokens

Test #3:

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

input:

3

output:

4
brb
rbr
rrr

result:

ok 4 tokens

Test #4:

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

input:

4

output:

6
bbrb
brbb
brbr
brrr
rbbr
rbrb
rbrr
rrbr
rrrb
rrrr

result:

ok 11 tokens

Test #5:

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

input:

5

output:

9
bbrbb
brbbr
brbrr
brrrb
rbbrb
rbrbr
rbrrr
rrbrb
rrrbr
rrrrr

result:

ok 11 tokens

Test #6:

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

input:

6

output:

12
bbbrbb
bbrbbb
bbrbbr
bbrbrr
bbrrrb
brbbbr
brbbrb
brbbrr
brbrbr
brbrrb
brbrrr
brrbrb
brrrbb
brrrbr
brrrrr
rbbbrb
rbbrbb
rbbrbr
rbbrrr
rbrbbr
rbrbrb
rbrbrr
rbrrbr
rbrrrb
rbrrrr
rrbbrb
rrbrbb
rrbrbr
rrbrrr
rrrbbr
rrrbrb
rrrbrr
rrrrbr
rrrrrb
rrrrrr

result:

ok 36 tokens

Test #7:

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

input:

7

output:

16
bbbrbbb
bbrbbbr
bbrbbrr
bbrbrrb
bbrrrbb
brbbbrb
brbbrbr
brbbrrr
brbrbrb
brbrrbr
brbrrrr
brrbrbb
brrrbbr
brrrbrr
brrrrrb
rbbbrbb
rbbrbbr
rbbrbrr
rbbrrrb
rbrbbrb
rbrbrbr
rbrbrrr
rbrrbrb
rbrrrbr
rbrrrrr
rrbbrbb
rrbrbbr
rrbrbrr
rrbrrrb
rrrbbrb
rrrbrbr
rrrbrrr
rrrrbrb
rrrrrbr
rrrrrrr

result:

ok 36 tokens

Test #8:

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

input:

8

output:

20
bbbbrbbb
bbbrbbbb
bbbrbbbr
bbbrbbrr
bbbrbrrb
bbbrrrbb
bbrbbbbr
bbrbbbrb
bbrbbbrr
bbrbbrbr
bbrbbrrb
bbrbbrrr
bbrbrbrb
bbrbrrbb
bbrbrrbr
bbrbrrrr
bbrrbrbb
bbrrrbbb
bbrrrbbr
bbrrrbrr
bbrrrrrb
brbbbbrb
brbbbrbb
brbbbrbr
brbbbrrr
brbbrbbr
brbbrbrb
brbbrbrr
brbbrrbr
brbbrrrb
brbbrrrr
brbrbbrb
brbrbrbb
...

result:

ok 101 tokens

Test #9:

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

input:

9

output:

25
bbbbrbbbb
bbbrbbbbr
bbbrbbbrr
bbbrbbrrb
bbbrbrrbb
bbbrrrbbb
bbrbbbbrb
bbrbbbrbr
bbrbbbrrr
bbrbbrbrb
bbrbbrrbr
bbrbbrrrr
bbrbrbrbb
bbrbrrbbr
bbrbrrbrr
bbrbrrrrb
bbrrbrbbb
bbrrrbbbr
bbrrrbbrr
bbrrrbrrb
bbrrrrrbb
brbbbbrbb
brbbbrbbr
brbbbrbrr
brbbbrrrb
brbbrbbrb
brbbrbrbr
brbbrbrrr
brbbrrbrb
brbbrrr...

result:

ok 101 tokens

Test #10:

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

input:

10

output:

30
bbbbbrbbbb
bbbbrbbbbb
bbbbrbbbbr
bbbbrbbbrr
bbbbrbbrrb
bbbbrbrrbb
bbbbrrrbbb
bbbrbbbbbr
bbbrbbbbrb
bbbrbbbbrr
bbbrbbbrbr
bbbrbbbrrb
bbbrbbbrrr
bbbrbbrbrb
bbbrbbrrbb
bbbrbbrrbr
bbbrbbrrrr
bbbrbrbrbb
bbbrbrrbbb
bbbrbrrbbr
bbbrbrrbrr
bbbrbrrrrb
bbbrrbrbbb
bbbrrrbbbb
bbbrrrbbbr
bbbrrrbbrr
bbbrrrbrrb
...

result:

ok 101 tokens

Test #11:

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

input:

11

output:

36
bbbbbrbbbbb
bbbbrbbbbbr
bbbbrbbbbrr
bbbbrbbbrrb
bbbbrbbrrbb
bbbbrbrrbbb
bbbbrrrbbbb
bbbrbbbbbrb
bbbrbbbbrbr
bbbrbbbbrrr
bbbrbbbrbrb
bbbrbbbrrbr
bbbrbbbrrrr
bbbrbbrbrbb
bbbrbbrrbbr
bbbrbbrrbrr
bbbrbbrrrrb
bbbrbrbrbbb
bbbrbrrbbbr
bbbrbrrbbrr
bbbrbrrbrrb
bbbrbrrrrbb
bbbrrbrbbbb
bbbrrrbbbbr
bbbrrrbbb...

result:

ok 101 tokens

Test #12:

score: 0
Accepted
time: 2ms
memory: 4184kb

input:

12

output:

42
bbbbbbrbbbbb
bbbbbrbbbbbb
bbbbbrbbbbbr
bbbbbrbbbbrr
bbbbbrbbbrrb
bbbbbrbbrrbb
bbbbbrbrrbbb
bbbbbrrrbbbb
bbbbrbbbbbbr
bbbbrbbbbbrb
bbbbrbbbbbrr
bbbbrbbbbrbr
bbbbrbbbbrrb
bbbbrbbbbrrr
bbbbrbbbrbrb
bbbbrbbbrrbb
bbbbrbbbrrbr
bbbbrbbbrrrr
bbbbrbbrbrbb
bbbbrbbrrbbb
bbbbrbbrrbbr
bbbbrbbrrbrr
bbbbrbbrrrr...

result:

ok 101 tokens

Test #13:

score: 0
Accepted
time: 2ms
memory: 4272kb

input:

13

output:

49
bbbbbbrbbbbbb
bbbbbrbbbbbbr
bbbbbrbbbbbrr
bbbbbrbbbbrrb
bbbbbrbbbrrbb
bbbbbrbbrrbbb
bbbbbrbrrbbbb
bbbbbrrrbbbbb
bbbbrbbbbbbrb
bbbbrbbbbbrbr
bbbbrbbbbbrrr
bbbbrbbbbrbrb
bbbbrbbbbrrbr
bbbbrbbbbrrrr
bbbbrbbbrbrbb
bbbbrbbbrrbbr
bbbbrbbbrrbrr
bbbbrbbbrrrrb
bbbbrbbrbrbbb
bbbbrbbrrbbbr
bbbbrbbrrbbrr
bbb...

result:

ok 101 tokens

Test #14:

score: -100
Wrong Answer
time: 1ms
memory: 4228kb

input:

14

output:

56

result:

wrong answer Unexpected EOF in the participants output