Submission #636415

#	Time	Username	Problem	Language	Result	Execution time	Memory
636415		Dec0Dedd	Binary Subsequences (info1cup17_binary)	C++14	100 / 100	738 ms	4304 KiB

binary

#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 / 43
• Subtask 2: 39 / 39
• Subtask 3: 18 / 18