oj.uz

Submission #401621

# Submission time Handle Problem Language Result Execution time Memory
401621 2021-05-10T14:58:49 Z Victor Hidden Sequence (info1cup18_hidden) C++17
100 / 100
 10 ms 328 KB 
#include "grader.h"

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define per(i, a, b) for (int i = b - 1; i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef long long ll;

const int INF = 1000000007;

vector<int> findSequence(int n) {
    vector<int> ans(n, -1);
    vi subseq;

    int left[2], taken[2];
    taken[0] = taken[1] = 0;

    int zeros, ones, len = n / 2 + 1, small = 0, big = 1;
    zeros = -1;

    rep(i, 1, len + 1) {
        subseq.pb(0);
        if (!isSubsequence(subseq)) {
            zeros = i - 1;
            break;
        }
    }

    if (zeros == -1) {
        subseq.clear();
        rep(i, 1, len + 1) {
            subseq.pb(1);
            if (!isSubsequence(subseq)) {
                ones = i - 1;
                break;
            }
        }
        zeros = n - ones;
        swap(small, big);

    } else
        ones = n - zeros;

    left[0]=zeros;
    left[1]=ones;

    per(i, 0, n) {
        vi query;
        int add;

        query.clear();
        rep(j, 0, left[big]) query.pb(big);
        rep(j, 0, taken[small] + 1) query.pb(small);

        if (sz(query) <= len) {
            if (isSubsequence(query))
                add = small;
            else
                add = big;
        }

        else {
            query.clear();
            rep(j, 0, left[small]) query.pb(small);
            rep(j, 0, taken[big] + 1) query.pb(big);

            if (isSubsequence(query))
                add = big;
            else
                add = small;
        }

        --left[add];
        ++taken[add];
        subseq.insert(subseq.begin(), add);
        ans[i] = add;
    }

    return ans;
}

Compilation message

hidden.cpp: In function 'std::vector<int> findSequence(int)':
hidden.cpp:71:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   71 |         if (sz(query) <= len) {
      |                       ^
hidden.cpp:54:15: warning: 'ones' may be used uninitialized in this function [-Wmaybe-uninitialized]
   54 |         zeros = n - ones;
      |         ~~~~~~^~~~~~~~~~
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 272 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 1 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 8 ms 328 KB Output is correct: Maximum length of a query = 83
2 Correct 8 ms 200 KB Output is correct: Maximum length of a query = 90
3 Correct 7 ms 200 KB Output is correct: Maximum length of a query = 96
4 Correct 7 ms 300 KB Output is correct: Maximum length of a query = 77
5 Correct 7 ms 300 KB Output is correct: Maximum length of a query = 95
6 Correct 6 ms 200 KB Output is correct: Maximum length of a query = 87
7 Correct 10 ms 292 KB Output is correct: Maximum length of a query = 97
8 Correct 7 ms 200 KB Output is correct: Maximum length of a query = 83
9 Correct 10 ms 304 KB Output is correct: Maximum length of a query = 101
10 Correct 7 ms 256 KB Output is correct: Maximum length of a query = 100
11 Correct 7 ms 200 KB Output is correct: Maximum length of a query = 96
12 Correct 6 ms 200 KB Output is correct: Maximum length of a query = 100
13 Correct 8 ms 304 KB Output is correct: Maximum length of a query = 101