結果
問題 | No.2893 Minahoshi (Hard) |
ユーザー |
|
提出日時 | 2024-09-13 23:19:30 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 4,464 bytes |
コンパイル時間 | 3,467 ms |
コンパイル使用メモリ | 236,368 KB |
実行使用メモリ | 29,372 KB |
最終ジャッジ日時 | 2024-09-13 23:19:55 |
合計ジャッジ時間 | 24,447 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | RE * 49 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define ll long long#define pii pair<int, int>#define pll pair<ll, ll>#define vi vector<int>#define vl vector<ll>#define ov4(a, b, c, d, name, ...) name#define rep3(i, a, b, c) for(ll i = (a); i < (b); i += (c))#define rep2(i, a, b) rep3(i, a, b, 1)#define rep1(i, n) rep2(i, 0, n)#define rep0(n) rep1(aaaaa, n)#define rep(...) ov4(__VA_ARGS__, rep3, rep2, rep1, rep0)(__VA_ARGS__)#define per(i, a, b) for(ll i = (a) - 1; i >= (b); i--)#define fore(e, v) for(auto &&e : v)#define all(a) begin(a), end(a)#define si(a) (int)(size(a))#define lb(v, x) (lower_bound(all(v), x) - begin(v))#define eb emplace_backtemplate <typename T, typename S> bool chmin(T &a, const S &b) { return a > b ? a = b, 1 : 0; }template <typename T, typename S> bool chmax(T &a, const S &b) { return a < b ? a = b, 1 : 0; }const int INF = 1e9 + 100;const ll INFL = 3e18 + 100;#define i128 __int128_tstruct _ {_() { cin.tie(0)->sync_with_stdio(0), cout.tie(0); }} __;vi lcp(string s) {vector<string> res;rep(i, si(s)) res.eb(s.substr(i));sort(all(res));vi ans;rep(i, si(res) - 1) {bool found = false;rep(j, 1, min(si(res[i]), si(res[i + 1])) + 1) {if(res[i].substr(0, j) != res[i + 1].substr(0, j)) {ans.eb(j - 1);found = true;break;}}if(!found) ans.eb(min(si(res[i]), si(res[i + 1])));}return ans;}template <typename T> ostream &operator<<(ostream &os, vector<T> v) {os << "[";fore(e, v) os << e << ", ";return os << "]";}template <typename T, typename S> ostream &operator<<(ostream &os, pair<T, S> p) { return os << "(" << p.first << ", " << p.second << ")"; }struct edge {int x, y, idx;};vector<edge> eulerian_path(vector<edge> es, int s, bool directed = false) {if(es.empty()) return {};int n = 0;fore(e, es) chmax(n, max(e.x, e.y) + 1);vector<vector<pair<edge, int>>> g(n);for(auto &e : es) {int p = si(g[e.y]);g[e.x].emplace_back(e, p);if(!directed) {int q = si(g[e.x]) - 1;swap(e.x, e.y);g[e.x].emplace_back(e, q);}}vector<edge> ord;stack<pair<int, edge>> st;st.emplace(s, edge{-1, -1, -1});while(st.size()) {int x = st.top().first;if(empty(g[x])) {ord.eb(st.top().second);st.pop();} else {auto e = g[x].back();g[x].pop_back();if(e.second == -1) continue;if(!directed) g[e.first.y][e.second].second = -1;st.emplace(e.first.y, e.first);}}ord.pop_back();reverse(begin(ord), end(ord));if(si(ord) != si(es)) return {};return ord;}int main() {int t;cin >> t;rep(t) {int n;cin >> n;if(n == 2) {cout << "ab" << endl;continue;}int m = 1;while((1 << m) + (m - 1) < n) m++;vector<edge> E;rep(b, 1 << (m - 1)) {rep(j, 2) {int nb = ((b << 1) | j) & ~(1 << m - 1);E.push_back(edge{(int)b, nb, (int)j});}}auto res = eulerian_path(E, 0, true);vi used(1 << m - 1);vector<vector<vi>> cycle(1 << m - 1);vector<edge> f;used[res[0].x] = true;rep(i, si(res)) {// cout << i << " " << res[i].x << " " << res[i].y << endl;if(used[res[i].y] and ((res[i].y) or res[i].x == res[i].y)) {vi t;int j = i;while(true) {t.eb(res[j].idx);if(res[j].y == res[i].x) break;j++;}cycle[res[i].x].eb(t);i = j;} else {f.eb(res[i]);used[res[i].y] = true;}}int rem = n - (m - 1) - (1 << m - 1);string s(m - 1, 'a');fore(e, f) {for(const vi &c : cycle[e.x]) {if((rem & si(c)) == si(c)) {fore(e, c) s += 'a' + e;rem -= si(c);}}s += 'a' + e.idx;}reverse(all(s));cout << s << endl;// cout << lcp(s) << endl;}}