oj.uz

답안 #401404

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
401404 2021-05-10T06:45:24 Z Victor Hidden Sequence (info1cup18_hidden) C++17
39 / 100
 9 ms 328 KB 
#include <bits/stdc++.h>

#include "grader.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;

    rep(k, 0, 2) {
        left[0] = zeros;
        left[1] = ones;
        taken[0] = taken[1] = 0;
        subseq.clear();

        per(i, (n + 1) / 2, n) {
            vi query = subseq;
            int add;
            query.insert(query.begin(), big);
            rep(j, 0, left[small]) query.insert(query.begin(), small);

            if (k) reverse(all(query));
            if (sz(query) <= len) {
                if (isSubsequence(query))
                    add = big;
                else
                    add = small;

            } else {
                query.clear();

                rep(j, 0, left[big]) query.pb(big);
                rep(j, 0, taken[small] + 1) query.pb(small);
                if (k) reverse(all(query));
                if (isSubsequence(query))
                    add = small;
                else
                    add = big;
            }

            --left[add];
            ++taken[add];
            subseq.insert(subseq.begin(), add);
            ans[k ? n - i - 1 : i] = add;
        }
    }

    if (n & 1) {
        rep(i, 0, n) if (ans[i] == 0)-- zeros;
        if (zeros)
            ans[n >> 1] = 0;
        else
            ans[n >> 1] = 1;
    }

    return ans;
}

Compilation message

hidden.cpp: In function 'std::vector<int> findSequence(int)':
hidden.cpp:73:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   73 |             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
15.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 1 ms 200 KB Output is partially correct: Maximum length of a query = 6
2 Partially correct 1 ms 200 KB Output is partially correct: Maximum length of a query = 7
3 Partially correct 1 ms 200 KB Output is partially correct: Maximum length of a query = 6
4 Correct 1 ms 200 KB Output is correct: Maximum length of a query = 5
5 Partially correct 1 ms 200 KB Output is partially correct: Maximum length of a query = 5

Subtask #2
24.0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 9 ms 200 KB Output is partially correct: Maximum length of a query = 94
2 Partially correct 9 ms 296 KB Output is partially correct: Maximum length of a query = 103
3 Partially correct 8 ms 328 KB Output is partially correct: Maximum length of a query = 104
4 Partially correct 9 ms 200 KB Output is partially correct: Maximum length of a query = 91
5 Partially correct 6 ms 200 KB Output is partially correct: Maximum length of a query = 111
6 Partially correct 5 ms 328 KB Output is partially correct: Maximum length of a query = 150
7 Partially correct 6 ms 328 KB Output is partially correct: Maximum length of a query = 112
8 Partially correct 6 ms 296 KB Output is partially correct: Maximum length of a query = 106
9 Partially correct 8 ms 328 KB Output is partially correct: Maximum length of a query = 108
10 Partially correct 9 ms 312 KB Output is partially correct: Maximum length of a query = 123
11 Partially correct 8 ms 328 KB Output is partially correct: Maximum length of a query = 97
12 Partially correct 8 ms 328 KB Output is partially correct: Maximum length of a query = 149
13 Partially correct 7 ms 292 KB Output is partially correct: Maximum length of a query = 106