oj.uz

Submission #46271

# Submission time Handle Problem Language Result Execution time Memory
46271 2018-04-18T13:28:59 Z qoo2p5 Hidden Sequence (info1cup18_hidden) C++17
39 / 100
 108 ms 576 KB 
#include <bits/stdc++.h>
#include "grader.h"

using namespace std;

typedef long long ll;

const int INF = (int) 1e9 + 1e6 + 123;
const ll LINF = (ll) 1e18 + 1e9 + 123;

#define rep(i, s, t) for (auto i = (s); i < (t); ++(i))
#define per(i, s, t) for (auto i = (s); i >= (t); --(i))
#define sz(x) ((int)(x).size())
#define mp make_pair
#define pb push_back

bool mini(auto &x, const auto &y) {
	if (y < x) {
		x = y;
		return 1;
	}
	return 0;
}

bool maxi(auto &x, const auto &y) {
	if (y > x) {
		x = y;
		return 1;
	}
	return 0;
}

bool rev;

bool ask(const vector<pair<int, int>> &what) {
	vector<int> res;
	for (auto it : what) {
		while (it.second--) {
			res.pb(it.first ^ rev);
		}
	}
	return isSubsequence(res);
}

vector<int> findSequence(int n) {
	int total_ones = 0;
	int total_zeros = 0;
	int k = n / 2 + 1;
	while (total_ones + 1 <= k && ask({{1, total_ones + 1}})) {
		total_ones++;
	}
	while (total_zeros + 1 <= k && ask({{0, total_zeros + 1}})) {
		total_zeros++;
	}
	
	if (total_ones < total_zeros) {
		total_zeros = n - total_ones;
	} else {
		total_ones = n - total_zeros;
	}
	
	if (total_zeros < total_ones) {
		rev = 1;
		swap(total_zeros, total_ones);
	}
	
	vector<int> pos1;
	
	rep(i, 0, total_ones) {
		int left1 = i;
		int right1 = total_ones - i - 1;
		int left0 = 0;
		while (1) {
			left0++;
			int right0 = total_zeros - left0;
			if (right0 < 0) {
				left0--;
				break;
			}
			
			int cnt1 = 0;//left0 + right1 + 1;
			int cnt2 = INF;//left1 + right0 + 1;
			
			bool ok = false;
			
			if (cnt1 <= k) {
				ok = ask({{0, left0}, {1, 1}, {1, right1}});
			} else {
				ok = ask({{1, left1}, {1, 1}, {0, right0}});
			}
			
			if (!ok) {
				left0--;
				break;
			}
		}
		pos1.pb(left1 + left0);
	}
	
	vector<int> ans(n);
	for (int i : pos1) {
		ans[i] = 1;
	}
	for (int &i : ans) {
		i ^= rev;
	}
	return ans;
}

Compilation message

hidden.cpp: In function 'std::vector<int> findSequence(int)':
hidden.cpp:82:8: warning: unused variable 'cnt2' [-Wunused-variable]
    int cnt2 = INF;//left1 + right0 + 1;
        ^~~~
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
15.0 / 20.0

# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 252 KB Output is partially correct: Maximum length of a query = 6
2 Partially correct 2 ms 456 KB Output is partially correct: Maximum length of a query = 7
3 Partially correct 2 ms 456 KB Output is partially correct: Maximum length of a query = 6
4 Correct 2 ms 456 KB Output is correct: Maximum length of a query = 5
5 Partially correct 2 ms 524 KB Output is partially correct: Maximum length of a query = 5

Subtask #2
24.0 / 80.0

# Verdict Execution time Memory Grader output
1 Partially correct 53 ms 524 KB Output is partially correct: Maximum length of a query = 94
2 Partially correct 81 ms 524 KB Output is partially correct: Maximum length of a query = 103
3 Partially correct 99 ms 524 KB Output is partially correct: Maximum length of a query = 106
4 Partially correct 59 ms 524 KB Output is partially correct: Maximum length of a query = 91
5 Partially correct 87 ms 524 KB Output is partially correct: Maximum length of a query = 111
6 Partially correct 80 ms 524 KB Output is partially correct: Maximum length of a query = 151
7 Partially correct 108 ms 524 KB Output is partially correct: Maximum length of a query = 128
8 Partially correct 49 ms 524 KB Output is partially correct: Maximum length of a query = 96
9 Partially correct 64 ms 564 KB Output is partially correct: Maximum length of a query = 121
10 Partially correct 90 ms 576 KB Output is partially correct: Maximum length of a query = 124
11 Partially correct 73 ms 576 KB Output is partially correct: Maximum length of a query = 97
12 Partially correct 101 ms 576 KB Output is partially correct: Maximum length of a query = 149
13 Partially correct 63 ms 576 KB Output is partially correct: Maximum length of a query = 106