oj.uz

Submission #636415

# Submission time Handle Problem Language Result Execution time Memory
636415 2022-08-29T08:39:44 Z Dec0Dedd Binary Subsequences (info1cup17_binary) C++14
100 / 100
 738 ms 4304 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 1e6+100;

int phi[N];

vector<int> ans;

void gen(int i, int j) {
   if (i == 0 && j == 0) return;
   if (i > j) ans.push_back(0), gen(i-j-1, j);
   else ans.push_back(1), gen(i, j-i-1);
}

int chk(int i, int j) {
   if (i == 0 && j == 0) return 0;
   if (i == j) return -1;
   if (i > j) {
      int k=i/(j+1), res=chk(i-(j+1)*k, j);
      if (res == -1) return -1;
      return res+k;
   } else {
      int k=j/(i+1), res=chk(i, j-(i+1)*k);
      if (res == -1) return -1;
      return res+k;
   }
}

void solve() {
   int k; cin>>k;
   ans.clear();

   int sz=INT_MAX, val=-1;
   for (int t=0; t<=k; ++t) {
      int x=chk(t, k-t);
      if (x != -1 && sz > x) sz=x, val=t;
   }

   assert(val != -1);
   cout<<phi[k+2]<<"\n";
   gen(val, k-val);
   for (auto u : ans) cout<<u<<" ";
   cout<<"\n";
}

int main() {
   ios_base::sync_with_stdio(0);
   cin.tie(NULL);
   cout.tie(NULL);
   
   for (int i=0; i<N; ++i) phi[i]=i;
   for (int i=2; i<N; ++i) {
      if (phi[i] == i) {
         for (int j=i; j<N; j+=i) phi[j]-=phi[j]/i;
      }
   }

   int t; cin>>t;
   while (t--) solve();
}

Subtask #1
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 4180 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 4212 KB Output is correct
2 Correct 95 ms 4216 KB Output is correct
3 Correct 86 ms 4220 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 734 ms 4304 KB Output is correct
2 Correct 736 ms 4216 KB Output is correct
3 Correct 738 ms 4300 KB Output is correct