Submission #388407

#	Time	Username	Problem	Language	Result	Execution time	Memory
388407		lukameladze	Binary Subsequences (info1cup17_binary)	C++14	100 / 100	675 ms	332 KiB

binary

# include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
using namespace std;
int t,raod,rem,cnt,xx,bb,x,y,k,ans,idx,mn,ww,anss1;
void go(int x, int y, int raod) {
     if (x==0 && y==0) {
          anss1=raod;
     }
     if (x==y && x!=0) anss1=-1;
     if (x>y) {
          bb=y+1;
          rem=x%bb;
          cnt=(x-rem)/bb;
          go(rem,y,raod+cnt);
     }
     if (x<y) {
          bb=x+1;
          rem=y%bb;
          cnt=(y-rem)/bb;
          go(x,rem,raod+cnt);
     }
}
void go1(int x, int y) {
     if (x==0 && y==0) return;
     if (x==y) return ;
     if (x>y) {
          cout<<0<<" ";
          go1(x-y-1, y);
     }
     else
     if (x<y) {
          cout<<1<<" ";
          go1(x,y-x-1);
     }
}
int main() {
     std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
     cin>>t;
     while (t--) {
          cin>>k;
          mn=1e9;ans=0;
          for (int x=0; x<=k/2; x++) {
               go(x,k-x,0);
               if (anss1!=-1) {
                    ans+=2;
                    if (mn>anss1) {
                         mn=anss1;
                         idx=x;
                    }
               }
          }
          cout<<ans<<endl;
          go1(idx,k-idx);
          cout<<endl;
     }
}

• Subtask 1: 43 / 43
• Subtask 2: 39 / 39
• Subtask 3: 18 / 18