/*input
20
*/
#include <bits/stdc++.h>
#ifndef UncleGrandpa
#include "grader.h"
#endif
using namespace std;
#define sp ' '
#define endl '\n'
#define fi first
#define se second
#define mp make_pair
#define __builtin_popcount __builtin_popcountll
#define bit(x,y) ((x>>y)&1LL)
#define loop(i,l,r) for(int i=(int)l; i<=(int)r; i++)
#define rloop(i,l,r) for(int i=(int)l; i>=(int)r; i--)
//const int N=;
#ifdef UncleGrandpa
template <class T1, class T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &a) {
return os << '(' << a.first << ", " << a.second << ')';
}
template <class T>
ostream &operator<<(ostream &os, const vector<T> &a) {
os << '[';
for (unsigned int i = 0; i < a.size(); i++)
os << a[i] << (i < a.size() - 1 ? ", " : "");
os << ']';
return os;
}
int read() {
int x; cin >> x; return x;
}
vector<int> ORI;
bool isSubsequence(vector<int> inp) {
assert(inp.size() <= ORI.size() / 2 + 1);
int it = 0;
loop(i, 0, ORI.size() - 1) {
if (it == inp.size()) return true;
it += (inp[it] == ORI[i]);
}
return (it == inp.size());
}
#endif
vector<int> findSequence(int _n) {
int n = _n;
pair<int, int> num = mp(0, 0);
loop(i, 0, 1) {
vector<int> cur;
loop(k, 1, n / 2 + 1) {
cur.push_back(i);
if (!isSubsequence(cur)) {
num = mp(i, k - 1);
break;
}
}
}
if (num.se == 0) {
vector<int> ret(n, num.fi ^ 1);
return ret;
}
vector<int> conseq(num.se + 1, 0);
loop(k, 1, num.se) {
int leftX = k - 1;
int rightX = num.se - k;
bool done = false;
loop(curl, 1, n / 2 - rightX) {
vector<int> cur;
loop(_, 1, curl) cur.push_back(num.fi ^ 1);
loop(_, 1, rightX + 1) cur.push_back(num.fi);
if (!isSubsequence(cur)) {
done = true;
conseq[k] = curl - 1;
break;
}
}
if (done) continue;
loop(curr, 1, n / 2 - leftX) {
vector<int> cur;
loop(_, 1, leftX + 1) cur.push_back(num.fi);
loop(_, 1, curr) cur.push_back(num.fi ^ 1);
if (!isSubsequence(cur)) {
done = true;
conseq[k] = n - num.se - (curr - 1);
break;
}
}
if (!done)
conseq[k] = n - num.se - (n / 2 - leftX);
}
vector<int> ret;
loop(i, 1, num.se) {
loop(_, 1, conseq[i] - conseq[i - 1]) ret.push_back(num.fi ^ 1);
ret.push_back(num.fi);
}
while (ret.size() < n) ret.push_back(num.fi ^ 1);
return ret;
}
#ifdef UncleGrandpa
signed main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int n = rd() % 1000 + 1;
// // cin >> n;
loop(i, 1, n) ORI.push_back(rd() % 2);
// cout << ORI << endl;
auto rec = findSequence(n);
if (rec == ORI) cout << "OK" << endl;
else {
cout << "WA" << endl;
cout << rec << endl << ORI << endl;
assert(false);
}
cout << rec << endl << ORI << endl;
}
#endif
Compilation message
hidden.cpp: In function 'std::vector<int> findSequence(int)':
hidden.cpp:99:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (ret.size() < n) ret.push_back(num.fi ^ 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++)
~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct: Maximum length of a query = 5 |
| 2 |
Correct |
3 ms |
256 KB |
Output is correct: Maximum length of a query = 6 |
| 3 |
Correct |
3 ms |
256 KB |
Output is correct: Maximum length of a query = 5 |
| 4 |
Correct |
3 ms |
256 KB |
Output is correct: Maximum length of a query = 5 |
| 5 |
Correct |
2 ms |
256 KB |
Output is correct: Maximum length of a query = 4 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
102 ms |
256 KB |
Output is correct: Maximum length of a query = 83 |
| 2 |
Correct |
145 ms |
328 KB |
Output is correct: Maximum length of a query = 90 |
| 3 |
Correct |
134 ms |
512 KB |
Output is correct: Maximum length of a query = 96 |
| 4 |
Correct |
41 ms |
384 KB |
Output is correct: Maximum length of a query = 77 |
| 5 |
Correct |
113 ms |
324 KB |
Output is correct: Maximum length of a query = 95 |
| 6 |
Correct |
75 ms |
320 KB |
Output is correct: Maximum length of a query = 87 |
| 7 |
Correct |
114 ms |
284 KB |
Output is correct: Maximum length of a query = 97 |
| 8 |
Correct |
74 ms |
384 KB |
Output is correct: Maximum length of a query = 83 |
| 9 |
Correct |
91 ms |
408 KB |
Output is correct: Maximum length of a query = 101 |
| 10 |
Correct |
131 ms |
384 KB |
Output is correct: Maximum length of a query = 100 |
| 11 |
Correct |
106 ms |
440 KB |
Output is correct: Maximum length of a query = 96 |
| 12 |
Correct |
66 ms |
512 KB |
Output is correct: Maximum length of a query = 100 |
| 13 |
Correct |
150 ms |
384 KB |
Output is correct: Maximum length of a query = 101 |
