oj.uz

답안 #496988

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
496988 2021-12-22T08:05:10 Z abc864197532 Hidden Sequence (info1cup18_hidden) C++17
39 / 100
 5 ms 328 KB 
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define mp make_pair
#define eb emplace_back
#define pb push_back
#define X first
#define Y second
#define pii pair<int,int>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T i, U ...j) {
	cout << i << ' ', abc(j...);
}
template <typename T> void printv(T l, T r) {
	for (; l != r; ++l) 
		cout << *l << " \n"[l + 1 == r];
}
#ifdef Doludu
#define test(x...) abc("[" + string(#x) + "]", x);
#include "grader.cpp"
#else
#define test(x...) void(0);
#endif
const int N = 1001;

bool isSubsequence (vector <int> S);

vector <int> reduce(vector <int> a) {
	vector <int> cur;
	int now = -1, cnt = 0;
	for (int i : a) {
		if (now == -1)
			now = i, cnt = 1;
		else if (now != i) {
			now = -1;
			cnt = 0;
			cur.pb(i);
		} else {
			cnt++;
		}
	}
	for (int i = 0; i < cnt; ++i)
		cur.pb(now);
	return cur;
}

vector <int> findSequence(int n) {
	int bound = n + 1 >> 1;
	int len = 0, d = 0;
	if (isSubsequence(vector <int>(bound, 0))) {
		d = 1;
	}
	for (int i = bound; i > 0; --i) {
		if (isSubsequence(vector <int>(i, d))) {
			len = i;
			break;
		}
	}
	vector <int> ans;
	for (int i = 0; i < n; ++i) {
		if (len == 0) {
			ans.pb(d ^ 1);
			continue;
		}
		if (len == n - i) {
			ans.pb(d);
			len--;
			continue;
		}
		vector <int> res = reduce(ans);
		res.pb(d ^ 1);
		for (int j = 0; j < len; ++j)
			res.pb(d);
		if (isSubsequence(res))
			ans.pb(d ^ 1);
		else
			ans.pb(d), len--;
	}
	return ans;
}

Compilation message

hidden.cpp: In function 'std::vector<int> findSequence(int)':
hidden.cpp:50:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |  int bound = n + 1 >> 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

# 결과 실행 시간 메모리 Grader output
1 Partially correct 0 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 2 ms 200 KB Output is partially correct: Maximum length of a query = 6
4 Correct 2 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 Correct 3 ms 296 KB Output is correct: Maximum length of a query = 83
2 Correct 4 ms 200 KB Output is correct: Maximum length of a query = 90
3 Partially correct 4 ms 200 KB Output is partially correct: Maximum length of a query = 98
4 Partially correct 5 ms 328 KB Output is partially correct: Maximum length of a query = 82
5 Partially correct 5 ms 200 KB Output is partially correct: Maximum length of a query = 102
6 Partially correct 3 ms 200 KB Output is partially correct: Maximum length of a query = 151
7 Partially correct 4 ms 200 KB Output is partially correct: Maximum length of a query = 128
8 Partially correct 3 ms 200 KB Output is partially correct: Maximum length of a query = 89
9 Correct 4 ms 200 KB Output is correct: Maximum length of a query = 101
10 Partially correct 3 ms 200 KB Output is partially correct: Maximum length of a query = 120
11 Partially correct 5 ms 200 KB Output is partially correct: Maximum length of a query = 97
12 Partially correct 2 ms 292 KB Output is partially correct: Maximum length of a query = 101
13 Partially correct 3 ms 300 KB Output is partially correct: Maximum length of a query = 106