제출 #389464

#제출 시각아이디문제언어결과실행 시간메모리
389464i_am_noobBinary Subsequences (info1cup17_binary)C++17
100 / 100
696 ms332 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long //#define int ll #define rep(n) rep1(i,n) #define rep1(i,n) rep2(i,0,n) #define rep2(i,a,b) for(int i=a; i<(b); ++i) #define rep3(i,a,b) for(int i=a; i>=(b); --i) #define pb push_back #define pii pair<int,int> #define sz(a) ((int)a.size()) #define all(a) a.begin(),a.end() #define pow2(x) (1ll<<(x)) #define inf 0x3f3f3f3f #ifdef i_am_noob #define bug(...) cerr << "#" << __LINE__ << " " << #__VA_ARGS__ << "- ", _do(__VA_ARGS__) template<typename T> void _do(T x){cerr << x << endl;} template<typename T, typename ...S> void _do(T x, S... y){cerr << x << ", ";_do(y...);} #else #define bug(...) 49 #endif const int maxn=2005,mod=1000000007; int t,n,cnt,minn,minid; signed main(){ ios_base::sync_with_stdio(0),cin.tie(0); cin >> t; while(t--){ cin >> n; n+=2; cnt=0; minn=inf; rep2(i,1,n) if(__gcd(i,n)==1){ if(2*i>n) break; cnt++; int a=n-i,b=i,x=0; while(a>1&&b>1){ x+=a/b; a%=b; swap(a,b); } if(a>b) x+=a-1; if(b>a) x+=b-1; if(x<minn) minn=x,minid=i; } cout << cnt*2 << "\n"; vector<int> vec; int a=minid,b=n-minid; while(a>1&&b>1){ if(a>b){ rep(a/b) vec.pb(1); a%=b; } else{ rep(b/a) vec.pb(0); b%=a; } } if(a>b) rep(a-1) vec.pb(1); if(b>a) rep(b-1) vec.pb(0); for(auto i: vec) cout << i << ' '; cout << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...