結果
問題 | No.2893 Minahoshi (Hard) |
ユーザー |
|
提出日時 | 2024-09-14 00:14:18 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 2,008 bytes |
コンパイル時間 | 4,346 ms |
コンパイル使用メモリ | 266,416 KB |
実行使用メモリ | 12,928 KB |
最終ジャッジ日時 | 2024-09-14 00:14:30 |
合計ジャッジ時間 | 11,827 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 23 WA * 22 RE * 4 |
ソースコード
#include <bits/stdc++.h>#include <ext/pb_ds/assoc_container.hpp>#include <ext/pb_ds/tree_policy.hpp>using namespace std;using namespace __gnu_pbds;#define PI acos(-1)#define LSB(i) ((i) & -(i))#define ll long long#define pb push_back#define mp make_pair#define mt make_tuple#define fi first#define sc second#define th third#define fo fourth#define pii pair<int,int>#define pll pair<ll,ll>#define ldb double#define INF 1e15#define MOD 1000000007#define endl "\n"#define all(data) data.begin(),data.end()#define TYPEMAX(type) std::numeric_limits<type>::max()#define TYPEMIN(type) std::numeric_limits<type>::min()#define MAXN 1000007ll p[MAXN],nxt[MAXN],cnt,k;bool vis[MAXN];void DFS(ll i){vis[i]=true;if(!vis[i*2%(1<<k)]) DFS(i*2%(1<<k));if(!vis[(i*2+1)%(1<<k)]) DFS((i*2+1)%(1<<k));p[++cnt]=i;}void solve() {ll n; cin>>n;k = 0;while((1<<k)+k<=n+1) k++;k--; DFS(0);ll ii=1,jj=cnt;while(ii<jj) swap(p[ii++],p[jj--]);if(n==(1<<k)+k-1){for(int i=1;i<k;i++) cout<<0;for(int i=1;i<=cnt;i++) cout<<char('a'+(p[i]&1));cout << '\n';return;}for(int i=0;i<(1<<(k+1));i++) {vis[i]=0; nxt[i]=-1;}for(int i=1;i<=cnt;i++){vis[p[i]=(p[i]<<1)|(p[i+1]&1)]=true;}for(int i=1;i<=cnt;i++) nxt[p[i]]=p[i%cnt+1];for(int i=0;i<(1<<(k+1));i++){if(nxt[i]<0) nxt[i]=nxt[i^(1<<k)]^1;}for(int i=0;i<(1<<(k+1));i++){if(!vis[i]){ii=i;while(!vis[ii]) {cnt++; vis[ii]=true; ii=nxt[ii];}swap(nxt[i],nxt[i^(1<<k)]);if(cnt+k>=n){for(int j=k;j+1;j--) cout<<char('a'+((nxt[i]>>j)&1));jj=nxt[nxt[i]];for(int j=k+2;j<=n;j++) {cout<<char('a'+(jj&1)); jj=nxt[jj];}cout << '\n';break;}}}}int main(){ios::sync_with_stdio(false); cin.tie(0);int t;cin >> t;while (t--) solve();return 0;}