oj.uz

Submission #46273

# Submission time Handle Problem Language Result Execution time Memory
46273 2018-04-18T13:43:43 Z qoo2p5 Hidden Sequence (info1cup18_hidden) C++17
100 / 100
 146 ms 572 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;
		bool found = false;
		
		while (1) {
			left0++;
			int right0 = total_zeros - left0;
			if (right0 < 0) {
				left0--;
				break;
			}
			
			int cnt = left0 + 1 + right1;
			
			if (cnt > k) {
				break;
			}
			
			if (!ask({{0, left0}, {1, 1}, {1, right1}})) {
				found = true;
				left0--;
				break;
			}
		}
		
		if (found) {
			pos1.pb(left1 + left0);
			continue;
		}
		
		int right0 = 0;
		while (1) {
			right0++;
			left0 = total_zeros - right0;
			if (left0 < 0) {
				right0--;
				break;
			}
			
			int cnt = left1 + 1 + right0;
			
			if (cnt > k) {
				break;
			}
			
			if (!ask({{1, left1}, {1, 1}, {0, right0}})) {
				found = true;
				right0--;
				break;
			}
		}
		
		//~ assert(found);
		if (!found) right0--;
		left0 = total_zeros - right0;
		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

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
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct: Maximum length of a query = 5
2 Correct 2 ms 308 KB Output is correct: Maximum length of a query = 6
3 Correct 2 ms 384 KB Output is correct: Maximum length of a query = 5
4 Correct 2 ms 420 KB Output is correct: Maximum length of a query = 5
5 Correct 2 ms 420 KB Output is correct: Maximum length of a query = 4

Subtask #2
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 420 KB Output is correct: Maximum length of a query = 83
2 Correct 84 ms 564 KB Output is correct: Maximum length of a query = 90
3 Correct 131 ms 564 KB Output is correct: Maximum length of a query = 96
4 Correct 69 ms 564 KB Output is correct: Maximum length of a query = 77
5 Correct 119 ms 564 KB Output is correct: Maximum length of a query = 95
6 Correct 98 ms 564 KB Output is correct: Maximum length of a query = 87
7 Correct 89 ms 564 KB Output is correct: Maximum length of a query = 97
8 Correct 46 ms 564 KB Output is correct: Maximum length of a query = 83
9 Correct 84 ms 572 KB Output is correct: Maximum length of a query = 101
10 Correct 139 ms 572 KB Output is correct: Maximum length of a query = 100
11 Correct 146 ms 572 KB Output is correct: Maximum length of a query = 96
12 Correct 59 ms 572 KB Output is correct: Maximum length of a query = 100
13 Correct 109 ms 572 KB Output is correct: Maximum length of a query = 101