oj.uz

Submission #636857

# Submission time Handle Problem Language Result Execution time Memory
636857 2022-08-30T10:21:56 Z Dec0Dedd Hidden Sequence (info1cup18_hidden) C++14
100 / 100
 66 ms 308 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 KB Output is correct: Maximum length of a query = 5
2 Correct 1 ms 208 KB Output is correct: Maximum length of a query = 6
3 Correct 1 ms 208 KB Output is correct: Maximum length of a query = 5
4 Correct 1 ms 208 KB Output is correct: Maximum length of a query = 5
5 Correct 1 ms 208 KB Output is correct: Maximum length of a query = 4

Subtask #2
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 208 KB Output is correct: Maximum length of a query = 83
2 Correct 40 ms 288 KB Output is correct: Maximum length of a query = 90
3 Correct 22 ms 208 KB Output is correct: Maximum length of a query = 96
4 Correct 23 ms 208 KB Output is correct: Maximum length of a query = 77
5 Correct 13 ms 300 KB Output is correct: Maximum length of a query = 95
6 Correct 7 ms 304 KB Output is correct: Maximum length of a query = 87
7 Correct 26 ms 308 KB Output is correct: Maximum length of a query = 97
8 Correct 17 ms 208 KB Output is correct: Maximum length of a query = 83
9 Correct 66 ms 208 KB Output is correct: Maximum length of a query = 101
10 Correct 47 ms 208 KB Output is correct: Maximum length of a query = 100
11 Correct 8 ms 308 KB Output is correct: Maximum length of a query = 96
12 Correct 8 ms 300 KB Output is correct: Maximum length of a query = 100
13 Correct 36 ms 208 KB Output is correct: Maximum length of a query = 101