oj.uz

Submission #261939

# Submission time Handle Problem Language Result Execution time Memory
261939 2020-08-12T08:07:32 Z thecodingwizard Hidden Sequence (info1cup18_hidden) C++11
100 / 100
 180 ms 256 KB 
#include<bits/stdc++.h>
#include "grader.h"

using namespace std;

bool qry(int zeroes, int ones, bool rev = false) {
    vector<int> v;
    for (int i = 0; i < zeroes; i++) {
        v.push_back(0);
    }
    for (int j = 0; j < ones; j++) {
        v.push_back(1);
    }
    if (rev) reverse(v.begin(), v.end());
    return isSubsequence(v);
}

vector<int> findSequence (int N)
{
    int numZeroes = 1, numOnes = 1;
    for (; numZeroes <= N/2+1; numZeroes++) {
        if (qry(numZeroes, 0)) {
            continue;
        } else {
            break;
        }
    }
    numZeroes--;
    if (numZeroes == N/2+1) {
        for (; numOnes <= N/2+1; numOnes++) {
            if (qry(0, numOnes, true)) {
                continue;
            } else {
                break;
            }
        }
        numOnes--;
        numZeroes = N - numOnes;
    } else {
        numOnes = N - numZeroes;
    }

    vector<int> ans;
    int usedZeroes = 0;

    for (int i = 0; i < numOnes; i++) {
        int newZeroes = 0;
        for (int j = 1; j <= numZeroes - usedZeroes; j++) {
            if (usedZeroes + j + numOnes - i <= N/2+1) {
                if (qry(usedZeroes + j, numOnes - i)) {
                    newZeroes++;
                } else {
                    break;
                }
            } else {
                if (qry(numZeroes - usedZeroes - j, i+1, true) && !qry(numZeroes - usedZeroes - (j-1), i+1, true)) {
                    newZeroes = j;
                } else {
                    continue;
                }
            }
        }
        for (int i = 0; i < newZeroes; i++) {
            ans.push_back(0);
        }
        ans.push_back(1);
        usedZeroes += newZeroes;
    }

    while ((int)ans.size() != N) {
        ans.push_back(0);
    }

    return ans;
}

Compilation message

grader.cpp: In function 'int main()':
grader.cpp:28:43: warning: format '%d' expects argument of type 'int', but argument 3 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
     fprintf (fifo_out, "%d\n", ans.size ());
                                ~~~~~~~~~~~^
grader.cpp:29:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     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 256 KB Output is correct: Maximum length of a query = 5
2 Correct 1 ms 256 KB Output is correct: Maximum length of a query = 6
3 Correct 1 ms 256 KB Output is correct: Maximum length of a query = 5
4 Correct 1 ms 256 KB Output is correct: Maximum length of a query = 5
5 Correct 1 ms 256 KB Output is correct: Maximum length of a query = 4

Subtask #2
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 256 KB Output is correct: Maximum length of a query = 83
2 Correct 84 ms 256 KB Output is correct: Maximum length of a query = 90
3 Correct 113 ms 256 KB Output is correct: Maximum length of a query = 96
4 Correct 49 ms 256 KB Output is correct: Maximum length of a query = 77
5 Correct 122 ms 256 KB Output is correct: Maximum length of a query = 95
6 Correct 44 ms 256 KB Output is correct: Maximum length of a query = 87
7 Correct 58 ms 256 KB Output is correct: Maximum length of a query = 97
8 Correct 44 ms 256 KB Output is correct: Maximum length of a query = 83
9 Correct 31 ms 256 KB Output is correct: Maximum length of a query = 101
10 Correct 29 ms 256 KB Output is correct: Maximum length of a query = 100
11 Correct 180 ms 256 KB Output is correct: Maximum length of a query = 96
12 Correct 94 ms 256 KB Output is correct: Maximum length of a query = 100
13 Correct 116 ms 256 KB Output is correct: Maximum length of a query = 101