QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#769896 | #6602. Journey to Un'Goro | daylight-et-al# | WA | 2ms | 4332kb | C++20 | 5.6kb | 2024-11-21 19:48:18 | 2024-11-21 19:48:24 |
Judging History
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));
}
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: 2ms
memory: 4276kb
input:
1
output:
1 r
result:
ok 2 tokens
Test #2:
score: 0
Accepted
time: 1ms
memory: 4152kb
input:
2
output:
2 br rb rr
result:
ok 4 tokens
Test #3:
score: 0
Accepted
time: 1ms
memory: 4024kb
input:
3
output:
4 brb rbr rrr
result:
ok 4 tokens
Test #4:
score: 0
Accepted
time: 1ms
memory: 4216kb
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: 4204kb
input:
5
output:
9 bbrbb brbbr brbrr brrrb rbbrb rbrbr rbrrr rrbrb rrrbr rrrrr
result:
ok 11 tokens
Test #6:
score: 0
Accepted
time: 2ms
memory: 4332kb
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: 2ms
memory: 4040kb
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: -100
Wrong Answer
time: 0ms
memory: 4164kb
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:
wrong answer Participant output contains extra tokens