Submission #636857

#	Time	Username	Problem	Language	Result	Execution time	Memory
636857		Dec0Dedd	Hidden Sequence (info1cup18_hidden)	C++14	100 / 100	66 ms	308 KiB

hidden

#include <bits/stdc++.h>
#include "grader.h"

using namespace std;

bool ask(int tp, int a, int b) {
   vector<int> tmp;
   while (a--) tmp.push_back(tp);
   tp^=1;
   while (b--) tmp.push_back(tp);
   return isSubsequence(tmp);
}

vector<int> findSequence(int n) {
   int lim=n/2+1, least=-1, k=-1, s[500]={};

   for (int i=0; i<=n/2; ++i) {
      if (ask(0, i+1, 0) == 0) {
         k=i, least=0;
         break;
      }

      if (ask(1, i+1, 0) == 0) {
         k=i, least=1;
         break;
      }
   }

   assert(k != -1 && least != -1);
   s[0]=0, s[k+1]=n-k;

   for (int i=1; i<=k; ++i) {
      s[i]=s[i-1];
      bool ok=true;

      while (s[i]+k+1-i <= lim) {
         ok=ask(least^1, s[i], k+1-i);
         if (!ok) {
            --s[i]; break;
         }
         ++s[i];
      }

      if (!ok) continue;
      int op=0;
      while (op+i <= lim) {
         ok=ask(least, i, op);
         if (!ok) {
            --op;
            break;
         }
         ++op;
      }

      if (!ok) s[i]=n-k-op;
      else s[i]=n-k-op+1;
   }

   for (int i=k+1; i>=1; --i) s[i]-=s[i-1];
   vector<int> ans;

   for (int i=1; i<=k+1; ++i) {
      while (s[i]--) ans.push_back(least^1);
      if (i != k+1) ans.push_back(least);
   }

   return ans;
}

Compilation message (stderr)

grader.cpp: In function 'int main()':
grader.cpp:28:26: warning: format '%d' expects argument of type 'int', but argument 3 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
   28 |     fprintf (fifo_out, "%d\n", ans.size ());
      |                         ~^     ~~~~~~~~~~~
      |                          |              |
      |                          int            std::vector<int>::size_type {aka long unsigned int}
      |                         %ld
grader.cpp:29:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for (int i=0; i<ans.size () && i < N; i++)
      |                   ~^~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 80 / 80