#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++)
~^~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
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 |
# |
결과 |
실행 시간 |
메모리 |
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 |