oj.uz

Submission #388406

# Submission time Handle Problem Language Result Execution time Memory
388406 2021-04-11T11:26:30 Z lukameladze Binary Subsequences (info1cup17_binary) C++14
82 / 100
 900 ms 328 KB 
# 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; x++) {
               go(x,k-x,0);
               if (anss1!=-1) {
                    ans++;
                    if (mn>anss1) {
                         mn=anss1;
                         idx=x;
                    }
               }
          }
          cout<<ans<<endl;
          go1(idx,k-idx);
          cout<<endl;
     }
}

Subtask #1
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 328 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 204 KB Output is correct
2 Correct 110 ms 204 KB Output is correct
3 Correct 104 ms 204 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1087 ms 288 KB Time limit exceeded
2 Halted 0 ms 0 KB -