oj.uz

답안 #46269

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
46269 2018-04-18T13:17:33 Z qoo2p5 Hidden Sequence (info1cup18_hidden) C++17
0 / 100
 48 ms 380 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 - 1;
			if (right0 < 0) {
				left0--;
				break;
			}
			
			int cnt1 = left0 + right1 + 1;
			int cnt2 = left1 + right0 + 1;
			
			assert(cnt1 <= k || cnt2 <= k);
			
			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

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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 248 KB Output is not correct: The returned sequence does not match the hidden one
2 Halted 0 ms 0 KB -

Subtask #2
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 48 ms 380 KB Output is not correct: The returned sequence does not match the hidden one
2 Halted 0 ms 0 KB -