oj.uz

답안 #343975

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
343975 2021-01-05T01:16:46 Z super_j6 Hidden Sequence (info1cup18_hidden) C++14
87 / 100
 8 ms 376 KB 
#include "grader.h"
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define endl '\n'
#define ll long long
#define pi pair<int, int>
#define f first
#define s second
#define vi vector<int>
/*
const int mxn = 200;
int n;
int b[mxn];
int ret;
 
bool isSubsequence(vi v){
	int x = 0;
	for(int i = 0; i < n && x < v.size(); i++) x += b[i] == v[x];
	return x == v.size();
}
*/
vi findSequence(int n){
	int x = 0, z = 0, m, k;
	vi a, v(n / 2 + 1, x);
	x ^= isSubsequence(v);
	
	v.assign(1, x);
	while(isSubsequence(v)) v.push_back(x);
	k = v.size() - 1;
	
	for(int i = 0; i <= k; i++){
		v[i] = !x;
		if(isSubsequence(v)) a.push_back(i);
		v[i] = x;
	}
	
	m = a.size();
	vi f, dp[2][m];
	f.resize(m);
	
	for(int i = 0; i < 2; i++){
		for(int j = 0; j < m; j++){
			if(j) dp[i][j].assign(abs(a[j - 1] - i * k) + 1, x);
			for(int l = j - 1, y = 1; ~l; l--){
				if(l != j - 1) y += abs(a[l + 1] - a[l]);
				if(dp[i][l].size() + y + 1 < dp[i][j].size()){
					dp[i][j] = dp[i][l];
					dp[i][j].push_back(!x);
					v.assign(y, x);
					dp[i][j].insert(dp[i][j].end(), v.begin(), v.end());
				}
			}
		}
		reverse(a.begin(), a.end());
	}
	reverse(dp[1], dp[1] + m);
	for(int j = 0; j < m; j++) reverse(dp[1][j].begin(), dp[1][j].end());
	
	
	for(int i = 0; i < m; i++){
		f[i] = 0;
		v = dp[0][i];
		v.push_back(!x);
		v.insert(v.end(), dp[1][i].begin(), dp[1][i].end());
		
		while(v.size() <= n / 2 + 2 && isSubsequence(v)){
			f[i]++;
			v.insert(v.begin() + dp[0][i].size(), !x);
		}
		if(v.size() > n / 2 + 2) f[i] = -1;
		else z += f[i];
		
		/*
		cout << a[i] << ": " << f[i] << endl;
		for(int l = 0; l < 2; l++){
			for(int j = 0; j < dp[l][i].size(); j++) cout << dp[l][i][j] << " ";
			cout << endl;
		}
		cout << endl;
		*/
	}
	
	vi ans;
	for(int i = 0; i < m; i++){
		if(!~f[i]) f[i] = n - k - z;
		v.assign(a[i] - (i ? a[i - 1] : 0), x);
		ans.insert(ans.end(), v.begin(), v.end());
		v.assign(f[i], !x);
		ans.insert(ans.end(), v.begin(), v.end());
	}
	v.assign(k - a.back(), x);
	ans.insert(ans.end(), v.begin(), v.end());
	
	return ans;
}
/*
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	
	for(int i = 0; i < n; i++) cin >> b[i];
	
	for(int i = 0; i < (1 << n); i++){
		for(int j = 0; j < n; j++) b[j] = (i >> j) & 1;
		vi v = findSequence(n);
		if(v.size() > n){
			cout << ret << endl;
			for(int j = 0; j < n; j++) cout << b[j] << " ";
			cout << endl;
			for(int j : v) cout << j << " ";
			cout << endl << endl;
		}
	}
 
	return 0;
}
*/

Compilation message

hidden.cpp: In function 'std::vector<int> findSequence(int)':
hidden.cpp:69:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   69 |   while(v.size() <= n / 2 + 2 && isSubsequence(v)){
      |         ~~~~~~~~~^~~~~~~~~~~~
hidden.cpp:73:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   73 |   if(v.size() > n / 2 + 2) f[i] = -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 1 ms 364 KB Output is partially correct: Maximum length of a query = 6
2 Partially correct 1 ms 364 KB Output is partially correct: Maximum length of a query = 7
3 Correct 1 ms 364 KB Output is correct: Maximum length of a query = 5
4 Partially correct 1 ms 364 KB Output is partially correct: Maximum length of a query = 6
5 Partially correct 1 ms 364 KB Output is partially correct: Maximum length of a query = 5

Subtask #2
72.0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 364 KB Output is correct: Maximum length of a query = 83
2 Correct 7 ms 364 KB Output is correct: Maximum length of a query = 90
3 Correct 6 ms 364 KB Output is correct: Maximum length of a query = 96
4 Correct 5 ms 364 KB Output is correct: Maximum length of a query = 77
5 Correct 6 ms 364 KB Output is correct: Maximum length of a query = 95
6 Correct 4 ms 376 KB Output is correct: Maximum length of a query = 87
7 Correct 5 ms 364 KB Output is correct: Maximum length of a query = 97
8 Correct 5 ms 364 KB Output is correct: Maximum length of a query = 83
9 Correct 6 ms 364 KB Output is correct: Maximum length of a query = 101
10 Correct 4 ms 376 KB Output is correct: Maximum length of a query = 100
11 Partially correct 8 ms 364 KB Output is partially correct: Maximum length of a query = 97
12 Correct 7 ms 364 KB Output is correct: Maximum length of a query = 100
13 Correct 7 ms 364 KB Output is correct: Maximum length of a query = 101