Submission #46273

#	Time	Username	Problem	Language	Result	Execution time	Memory
46273		qoo2p5	Hidden Sequence (info1cup18_hidden)	C++17	100 / 100	146 ms	572 KiB

hidden

#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 (stderr)

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 / 20
• Subtask 2: 80 / 80