oj.uz

Submission #69604

# Submission time Handle Problem Language Result Execution time Memory
69604 2018-08-21T09:50:10 Z Mamnoon_Siam Hidden Sequence (info1cup18_hidden) C++17
24 / 100
 93 ms 684 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 93 ms 248 KB Output is not correct: The returned sequence does not match the hidden one
2 Halted 0 ms 0 KB -

Subtask #2
24.0 / 80.0

# Verdict Execution time Memory Grader output
1 Partially correct 10 ms 308 KB Output is partially correct: Maximum length of a query = 165
2 Partially correct 9 ms 512 KB Output is partially correct: Maximum length of a query = 178
3 Partially correct 13 ms 512 KB Output is partially correct: Maximum length of a query = 190
4 Partially correct 6 ms 536 KB Output is partially correct: Maximum length of a query = 153
5 Partially correct 14 ms 536 KB Output is partially correct: Maximum length of a query = 188
6 Partially correct 6 ms 536 KB Output is partially correct: Maximum length of a query = 172
7 Partially correct 13 ms 544 KB Output is partially correct: Maximum length of a query = 192
8 Partially correct 9 ms 560 KB Output is partially correct: Maximum length of a query = 164
9 Partially correct 14 ms 560 KB Output is partially correct: Maximum length of a query = 200
10 Partially correct 7 ms 684 KB Output is partially correct: Maximum length of a query = 199
11 Partially correct 10 ms 684 KB Output is partially correct: Maximum length of a query = 190
12 Partially correct 9 ms 684 KB Output is partially correct: Maximum length of a query = 199
13 Partially correct 9 ms 684 KB Output is partially correct: Maximum length of a query = 200