oj.uz

Submission #493763

# Submission time Handle Problem Language Result Execution time Memory
493763 2021-12-12T20:28:28 Z Habitus Hidden Sequence (info1cup18_hidden) C++14
100 / 100
 137 ms 288 KB 
#include "grader.h"
#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define dec(x, y) fixed << setprecision((y)) << (x)
#define xx first
#define yy second
#define srt(v) sort((v).begin(), (v).end())
#define srtr(v) sort((v).rbegin(), (v).rend())
#define pb push_back
#define popb pop_back
#define sz(a) (int)(a).size()
#define len(a) (int)(a).length()
#define mp make_pair

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

/*static int maxQ = 0;
static vector < int > theRealAnswer;*/

bool nasao, nasao1;
int d, je, gde[200];
/*bool isSubsequence (vector < int > v)
{
    if (v.size () > maxQ)
        maxQ = v.size ();
    int i = 0;
    for (auto it : v)
    {
        while (i < theRealAnswer.size () && it != theRealAnswer[i]) i ++;
        if (i == theRealAnswer.size ()) return 0;
        i ++;
    }
    return 1;
}*/
vector<int> findSequence(int N) {
    d=N/2+1;
    vector<int> v;
    for(int i=1; i<=d; i++) {
        v.pb(1);
        bool da=isSubsequence(v);
        if(!da) {
            je=i-1;
            nasao=1;
            break;
        }
    }
    if(!nasao) {
        v.clear();
        for(int i=1; i<=d; i++) {
            v.pb(0);
            bool da=isSubsequence(v);
            if(!da) {
                je=N-i+1;
                break;
            }
        }
    }
    for(int a=0; a<je; a++) {
        nasao=nasao1=0;
        for(int i=0; i+je-a<=d; i++) {
            v.clear();
            for(int j=0; j<i; j++) v.pb(0);
            for(int j=0; j<je-a; j++) v.pb(1);
            bool da=isSubsequence(v);
            if(!da) {
                gde[a]=i+a-1;
                nasao=nasao1=1;
                break;
            }
        }
        if(!nasao) {
            v.clear();
            for(int j=0; j<a; j++) v.pb(1);
            for(int i=0; i+a+1<=d; i++) {
                if(i==0) v.pb(1);
                else v.pb(0);
                bool da=isSubsequence(v);
                if(!da) {
                    gde[a]=N+1-je-i+a;
                    nasao1=1;
                    break;
                }
            }
        }
        if(!nasao1) {
            gde[a]=d-je+2*a;
        }
    }
    v.assign(N, 0);
    for(int i=0; i<je; i++) {
        v[gde[i]]=1;
    }
    return v;
}
/*int main ()
{
int n, x;
scanf ("%d", &n), maxQ = 0;
for (int i=1; i<=n; i++)
    scanf ("%d", &x), theRealAnswer.push_back (x);

vector < int > ans = findSequence (n);
if (ans.size () != theRealAnswer.size ())
{
    printf ("Different lengths\n");
    for (auto it : ans)
        printf ("%d ", it);
    printf ("\n");
    return 0;
}

for (int i=0; i<ans.size (); i++)
    if (ans[i] != theRealAnswer[i])
    {
        printf ("WA position %d\n", i + 1);
        for (auto it : ans)
            printf ("%d ", it);
        printf ("\n");
        return 0;
    }
printf ("Ok, biggest queried length %d\n", maxQ);
return 0;
}
*/

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 200 KB Output is correct: Maximum length of a query = 5
2 Correct 1 ms 200 KB Output is correct: Maximum length of a query = 6
3 Correct 0 ms 200 KB Output is correct: Maximum length of a query = 5
4 Correct 1 ms 200 KB Output is correct: Maximum length of a query = 5
5 Correct 1 ms 200 KB Output is correct: Maximum length of a query = 4

Subtask #2
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 200 KB Output is correct: Maximum length of a query = 83
2 Correct 90 ms 276 KB Output is correct: Maximum length of a query = 90
3 Correct 119 ms 288 KB Output is correct: Maximum length of a query = 96
4 Correct 80 ms 200 KB Output is correct: Maximum length of a query = 77
5 Correct 117 ms 200 KB Output is correct: Maximum length of a query = 95
6 Correct 63 ms 272 KB Output is correct: Maximum length of a query = 87
7 Correct 79 ms 200 KB Output is correct: Maximum length of a query = 97
8 Correct 56 ms 200 KB Output is correct: Maximum length of a query = 83
9 Correct 69 ms 200 KB Output is correct: Maximum length of a query = 101
10 Correct 78 ms 200 KB Output is correct: Maximum length of a query = 100
11 Correct 137 ms 200 KB Output is correct: Maximum length of a query = 96
12 Correct 68 ms 200 KB Output is correct: Maximum length of a query = 100
13 Correct 89 ms 200 KB Output is correct: Maximum length of a query = 101