oj.uz

Submission #490849

# Submission time Handle Problem Language Result Execution time Memory
490849 2021-11-29T13:45:29 Z keta_tsimakuridze Hidden Sequence (info1cup18_hidden) C++14
0 / 100
 400 ms 1624 KB 
#include<bits/stdc++.h>
#include "grader.h"
#define f first
#define s second
#define pii pair<int,int>
using namespace std;
const int N = 200 + 5, mod = 1e9 + 7; // !
int t, dp[N][N], n, a[N];
/*
bool isSubsequence(vector<int> x) {
	dp[0][0] = 1;
 
	for(int i = 1; i <= n; i++) {
		dp[i][0] = 1;
		for(int j = 1; j <= x.size(); j++) {
			dp[i][j] = dp[i - 1][j] | (dp[i - 1][j - 1] && a[i] == x[j - 1]);
		}
	}
	return dp[n][x.size()];
} */
int get(int t) {
	int ans = -1;
	vector<int> x;
	for(int i = 1; i <= n / 2 + 1; i++) {
		x.push_back(t);
		if(!isSubsequence(x)) {
			ans = i - 1;
			break;
		}
	}
	return ans;
}
vector<int> tr(vector<int> x, int t) {
	for(int i = 0; i < x.size(); i++) x[i] ^= t;
	return x;
}
vector<int> findSequence(int n) {
	int cnt0 = -1, cnt1 = 0, t = 0;
	cnt0 = get(0);
	if(cnt0 == -1) {
		t = 1;
		cnt0 = get(1);
	}
	cnt1 = n - cnt0;
	int cur = 0; vector<int> ans;
	for(int i = 1; i <= cnt1; i++) {
		while(true) {
			// 00000 0 11111
			if(cur == cnt0) {
				ans.push_back(1); break;
			}
			if(cur + cnt1 - i + 2 <= n/2) { //cout << "++" << i << endl;
				vector<int> x;
				for(int j = 1; j <= cur + 1; j++) x.push_back(0);
				for(int j = 1; j <= cnt1 - i + 1; j++) x.push_back(1);
 
				if(isSubsequence(tr(x, t))) { 
				cur++;	ans.push_back(0);
				} else {
					ans.push_back(1);
					break;
				}
			}
			else { 
				vector<int> x;
				
				for(int j = 1; j <= i; j++) x.push_back(1);
				for(int j = 1; j <= cnt0 - cur; j++) x.push_back(0);
				if(isSubsequence(tr(x, t))) {
					ans.push_back(1); 
					break;
				}
				else {
				cur++;
				ans.push_back(0);
				}
			}
 
		}

	}
	
	while(cur < cnt0) ans.push_back(0), cur++;
	ans = tr(ans, t);
	return ans;
}
/*
main() {
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	vector<int> x = findSequence(n);
	for(int i = 0; i < x.size(); i++) cout << x[i] <<" ";
}
*/

Compilation message

hidden.cpp: In function 'std::vector<int> tr(std::vector<int>, int)':
hidden.cpp:34:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  for(int i = 0; i < x.size(); i++) x[i] ^= t;
      |                 ~~^~~~~~~~~~
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
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2414 ms 1624 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1704 ms 980 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -