Submission #69604

#	Time	Username	Problem	Language	Result	Execution time	Memory
69604		Mamnoon_Siam	Hidden Sequence (info1cup18_hidden)	C++17	24 / 100	93 ms	684 KiB

hidden

#include<bits/stdc++.h>
#include "grader.h"
using namespace std;

vector<int> make(int ones, vector<int> zs) {
	vector<int> ret;
	for(int i = 0; i < zs[0]; i++)
		ret.emplace_back(0);
	for(int i = 1; i < zs.size(); i++) {
		ret.emplace_back(1);
		for(int j = 0; j < zs[i]; j++)
			ret.emplace_back(0);
	} return ret;
}

int ask(int N, vector<int> vec) {
	if(vec.size() > N) return 0;
	return isSubsequence(vec);
}

int issub(vector<int> s, vector<int> t) {
	int i = 0;
	for (auto it : t) {
		while (i < s.size () and it != s[i]) i++;
		if (i == s.size ()) return 0;
		i++;
	}
	return 1;
}

vector <int> findSequence (int N) {
	if(N <= 10) {
		for(int mask = 0; mask < (1 << N); mask++) {
			vector<int> v;
			for(int i = 0; i < N; i++) {
				if(mask & (1 << i)) v.emplace_back(1);
				else v.emplace_back(0);
			}
			int req = N / 2 + 1;
			int flag = 1;
			for(int mask2 = 0; mask2 < (1 << N); mask2++) {
				if(__builtin_popcount(mask2) > req) continue;
				vector<int> t;
				for(int i = 0; i < N; i++) {
					if(mask2 & (1 << i))
						t.emplace_back(v[i]);
				}
				if(issub(v, t) != ask(N, t)) {
					flag = 0;
					break;
				}
			}
			if(flag) {
				return v;
			}
		}
	}
	int ones = 0;
	for(int i = 1; i <= N; i++) {
		if(ask(N, make(i, vector<int>(i + 1, 0)))) {
			ones = i;
		} else break;
	}
	vector<int> zs(ones + 1, 0);
	for(int it = 0; it < zs.size(); it++) {
		for(zs[it] = 1; ask(N, make(ones, zs)); zs[it]++) {}
		zs[it]--;
	}
	return make(ones, zs);
}

Compilation message (stderr)

hidden.cpp: In function 'std::vector<int> make(int, std::vector<int>)':
hidden.cpp:9:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 1; i < zs.size(); i++) {
                 ~~^~~~~~~~~~~
hidden.cpp: In function 'int ask(int, std::vector<int>)':
hidden.cpp:17:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(vec.size() > N) return 0;
     ~~~~~~~~~~~^~~
hidden.cpp: In function 'int issub(std::vector<int>, std::vector<int>)':
hidden.cpp:24:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (i < s.size () and it != s[i]) i++;
          ~~^~~~~~~~~~~
hidden.cpp:25:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (i == s.size ()) return 0;
       ~~^~~~~~~~~~~~
hidden.cpp: In function 'std::vector<int> findSequence(int)':
hidden.cpp:65:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int it = 0; it < zs.size(); it++) {
                  ~~~^~~~~~~~~~~
grader.cpp: In function 'int main()':
grader.cpp:28:43: warning: format '%d' expects argument of type 'int', but argument 3 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
     fprintf (fifo_out, "%d\n", ans.size ());
                                ~~~~~~~~~~~^
grader.cpp:29:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<ans.size () && i < N; i++)
                   ~^~~~~~~~~~~~

• Subtask 1: 0 / 20
• Subtask 2: 24 / 80