oj.uz

Submission #1100830

# Submission time Handle Problem Language Result Execution time Memory
1100830 2024-10-14T18:49:52 Z Kirill22 Hidden Sequence (info1cup18_hidden) C++17
59 / 100
 7 ms 592 KB 
#include "bits/stdc++.h"

using namespace std;

bool isSubsequence (vector < int > v);

vector<int> findSequence(int N) {
    int mx = N / 2 + 1;
    vector<int> cnt(2);
    for (int t = 0; t < 2; t++) {
        for (int i = 1; i <= mx; i++) {
            vector<int> qu(i, t);
            if (isSubsequence(qu)) {
                cnt[t] = i;
            } else {
                break;
            }
        }
    }
    int t = 0;
    if (cnt[0] > cnt[1]) {
        cnt[0] - N - cnt[1];
        t = 1;
    } else {
        cnt[1] = N - cnt[0];
        t = 0;
    }
    vector<int> lens(cnt[t] + 1);
    for (int j = 1; j <= mx; j++) {
        int good = 0;
        for (int i = 0; i <= cnt[t]; i++) {
            if (lens[i] == j - 1) {
                vector<int> qu(i, t);
                for (int k = 0; k < j; k++) {
                    qu.push_back(1 - t);
                }
                for (int k = 0; k < cnt[t] - i; k++) {
                    qu.push_back(t);
                }
                if (isSubsequence(qu)) {
                    lens[i] = j;
                    good++;
                }
            }
        }
        if (good <= 1) {
            break;
        }
    }
    int pos = std::max_element(lens.begin(), lens.end()) - lens.begin();
    int S = std::accumulate(lens.begin(), lens.end(), 0);
    lens[pos] = N - (cnt[t] + (S - lens[pos]));
    vector<int> answer(lens[0], 1 - t);
    for (int i = 1; i <= cnt[t]; i++) {
        answer.push_back(t);
        for (int j = 0; j < lens[i]; j++) {
            answer.push_back(1 - t);
        }
    }
    return answer;
}

//static int maxQ = 0;
//static vector < int > theRealAnswer;
//
//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;
//}
//
//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

hidden.cpp: In function 'std::vector<int> findSequence(int)':
hidden.cpp:22:20: warning: value computed is not used [-Wunused-value]
   22 |         cnt[0] - N - cnt[1];
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
15.0 / 20.0

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

Subtask #2
44.0 / 80.0

# Verdict Execution time Memory Grader output
1 Partially correct 4 ms 336 KB Output is partially correct: Maximum length of a query = 85
2 Correct 4 ms 336 KB Output is correct: Maximum length of a query = 90
3 Partially correct 5 ms 448 KB Output is partially correct: Maximum length of a query = 101
4 Partially correct 4 ms 444 KB Output is partially correct: Maximum length of a query = 81
5 Partially correct 5 ms 464 KB Output is partially correct: Maximum length of a query = 103
6 Partially correct 6 ms 336 KB Output is partially correct: Maximum length of a query = 130
7 Partially correct 4 ms 336 KB Output is partially correct: Maximum length of a query = 144
8 Partially correct 4 ms 592 KB Output is partially correct: Maximum length of a query = 86
9 Partially correct 7 ms 336 KB Output is partially correct: Maximum length of a query = 126
10 Partially correct 5 ms 336 KB Output is partially correct: Maximum length of a query = 125
11 Partially correct 4 ms 592 KB Output is partially correct: Maximum length of a query = 97
12 Partially correct 5 ms 444 KB Output is partially correct: Maximum length of a query = 150
13 Partially correct 5 ms 336 KB Output is partially correct: Maximum length of a query = 107