Submission #490851

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
490851	2021-11-29T13:49:09 Z	keta_tsimakuridze	Hidden Sequence (info1cup18_hidden)	C++14	Compilation error	0 ms	0 KB

hidden

#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) {
		           assert(ans.size() <= n);
			// 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 'bool isSubsequence(std::vector<int>)':
hidden.cpp:14:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |   for(int j = 1; j <= x.size(); j++) {
      |                  ~~^~~~~~~~~~~
hidden.cpp: In function 'std::vector<int> tr(std::vector<int>, int)':
hidden.cpp:33:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  for(int i = 0; i < x.size(); i++) x[i] ^= t;
      |                 ~~^~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from hidden.cpp:1:
hidden.cpp: In function 'std::vector<int> findSequence(int)':
hidden.cpp:47:32: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   47 |              assert(ans.size() <= n);
      |                     ~~~~~~~~~~~^~~~
hidden.cpp: At global scope:
hidden.cpp:88:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   88 | main() {
      | ^~~~
hidden.cpp: In function 'int main()':
hidden.cpp:92:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |  for(int i = 0; i < x.size(); i++) cout << x[i] <<" ";
      |                 ~~^~~~~~~~~~
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++)
      |                   ~^~~~~~~~~~~~
/usr/bin/ld: /tmp/ccKVVH9f.o: in function `isSubsequence(std::vector<int, std::allocator<int> >)':
grader.cpp:(.text+0x0): multiple definition of `isSubsequence(std::vector<int, std::allocator<int> >)'; /tmp/ccDdJMoh.o:hidden.cpp:(.text+0x0): first defined here
/usr/bin/ld: /tmp/ccKVVH9f.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccDdJMoh.o:hidden.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status