#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;
// #define LOCAL
#ifdef LOCAL
bool isSubsequence (vector <int> v);
#else
#include "grader.h"
#endif
bool flip = 0;
int N, x, mxlen;
vi ans, done, num;
void trans(vi& x) { for (int& i: x) i ^= 1; }
bool get(vi v) {
if (flip) trans(v);
#ifdef LOCAL
F0R(i,sz(num)) {
cout << " ";
if (done[i]) cout << "[";
else cout << '(';
F0R(j,num[i]) cout << '1';
if (done[i]) cout << ']';
else cout << ')';
cout << " ";
if (i != sz(num)-1) cout << "0";
}
cout << "QUERY ";
for (int i: v) cout << i << " ";
cout << "\n";
#endif
return isSubsequence(v);
}
vi mul(int x, int len) {
vi v; F0R(i,len) v.pb(x);
return v;
}
int getNum0() {
int num = mxlen;
while (num && !isSubsequence(mul(0,num))) num --;
if (num == mxlen) {
while (num && !isSubsequence(mul(1,num))) num --;
num = N-num;
}
return num;
}
vi actual(vi v) {
if (sz(v) == 0) return {};
int nex[sz(v)+1][2];
nex[sz(v)][0] = nex[sz(v)][1] = sz(v);
F0Rd(i,sz(v)) {
nex[i][0] = nex[i+1][0], nex[i][1] = nex[i+1][1];
if (v[i] == 0) nex[i][0] = i;
if (v[i] == 1) nex[i][1] = i;
}
vi ret = {0};
int i = nex[0][0]+1;
while (i < sz(v)) {
if (nex[i][0] == sz(v)) i ++, ret.pb(1);
else if (nex[i][1] == sz(v)) {
if (ret.back() == 0) break;
i ++, ret.pb(0);
} else {
if (nex[i][0] > nex[i][1]) i = nex[i][0]+1, ret.pb(0);
else i = nex[i][1]+1, ret.pb(1);
}
}
return ret;
}
bool allZero(vi v) {
for (int i: v) if (i) return 0;
return 1;
}
vi compress(vi v) {
if (allZero(v)) return {};
vi cur, ans;
for (int i: v) {
if (i == -1) {
cur = actual(cur);
ans.insert(ans.end(),all(cur));
cur.clear();
} else cur.pb(i);
}
cur = actual(cur);
ans.insert(ans.end(),all(cur));
return ans;
}
vi getRep(int pos) {
vi t0;
F0R(i,pos) {
if (!done[i]) {
if (num[i] == 0) t0.pb(-1);
else t0.pb(1), t0.pb(1);
} else F0R(j,num[i]) t0.pb(1);
t0.pb(0);
}
t0 = compress(t0);
vi v;
F0R(i,num[pos]+1) v.pb(1);
vi t1;
FOR(i,pos+1,sz(num)) {
t1.pb(0);
if (!done[i]) {
if (num[i] == 0) t1.pb(-1);
else t1.pb(1), t1.pb(1);
} else F0R(j,num[i]) t1.pb(1);
}
reverse(all(t1));
t1 = compress(t1);
reverse(all(t1));
t0.insert(t0.end(),all(v));
t0.insert(t0.end(),all(t1));
return t0;
}
void dosmth() {
vpi posi;
F0R(i,x+1) if (!done[i]) {
/*cout << "??\n";
for (int j: getRep(i)) cout << j << " ";
cout << "\n";
cout << i << " " << sz(getRep(i)) << "\n";*/
posi.pb({sz(getRep(i)),i});
}
sort(all(posi));
if (posi[0].f > mxlen) {
cout << "\nOOPS " << posi[0].s << "\n";
for (int i: getRep(posi[0].s)) cout << i << " ";
cout << "\n\n";
}
bool x = get(getRep(posi[0].s));
// cout << posi[0].s << " " << x << " " << num[posi[0].s] << "\n";
if (x) num[posi[0].s] ++;
else done[posi[0].s] = 1;
}
vi findSequence (int n) {
N = n, mxlen = N/2+1;
x = getNum0();
if (x > N/2) {
flip = 1;
x = N-x;
}
done.resize(x+1), num.resize(x+1);
while (1) {
int sum = x;
vi bad;
F0R(i,x+1) {
if (!done[i]) bad.pb(i);
sum += num[i];
}
// cout << "OH " << sum << "\n";
if (sum == N) break;
if (sz(bad) == 1) {
num[bad[0]] += N-sum;
break;
}
dosmth();
}
F0R(i,x+1) {
F0R(j,num[i]) ans.pb(1);
if (i != x) ans.pb(0);
}
if (flip) trans(ans);
return ans;
}
#ifdef LOCAL
static int maxQ = 0;
static vector < int > theRealAnswer;
bool isSubsequence (vector < int > v) {
if (v.size () > maxQ)
maxQ = v.size ();
int i = 0;
for (auto it : v) {
while (i < theRealAnswer.size () && it != theRealAnswer[i]) i ++;
if (i == theRealAnswer.size ()) return 0;
i ++;
}
return 1;
}
int main ()
{
int n, x;
scanf ("%d", &n), maxQ = 0;
for (int i=1; i<=n; i++)
scanf ("%d", &x), theRealAnswer.push_back (x);
vector < int > ans = findSequence (n);
if (ans.size () != theRealAnswer.size ())
{
printf ("Different lengths\n");
for (auto it : ans)
printf ("%d ", it);
printf ("\n");
return 0;
}
for (int i=0; i<ans.size (); i++)
if (ans[i] != theRealAnswer[i])
{
printf ("WA position %d\n", i + 1);
for (auto it : ans)
printf ("%d ", it);
printf ("\n");
printf("Real: ");
for (int j: theRealAnswer) printf("%d ",j);
printf ("\n");
return 0;
}
printf ("Ok, biggest queried length %d\n", maxQ);
for (int j: theRealAnswer) printf("%d ",j);
printf ("\n");
return 0;
}
#else
#endif
/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( )
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/
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++)
~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 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 |
3 ms |
384 KB |
Output is correct: Maximum length of a query = 5 |
| 4 |
Correct |
3 ms |
384 KB |
Output is correct: Maximum length of a query = 5 |
| 5 |
Correct |
2 ms |
460 KB |
Output is correct: Maximum length of a query = 4 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
128 ms |
512 KB |
Output is correct: Maximum length of a query = 83 |
| 2 |
Correct |
127 ms |
564 KB |
Output is correct: Maximum length of a query = 90 |
| 3 |
Correct |
185 ms |
564 KB |
Output is correct: Maximum length of a query = 96 |
| 4 |
Correct |
90 ms |
564 KB |
Output is correct: Maximum length of a query = 77 |
| 5 |
Correct |
156 ms |
564 KB |
Output is correct: Maximum length of a query = 95 |
| 6 |
Correct |
57 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 |
74 ms |
564 KB |
Output is correct: Maximum length of a query = 83 |
| 9 |
Correct |
139 ms |
564 KB |
Output is correct: Maximum length of a query = 101 |
| 10 |
Correct |
121 ms |
564 KB |
Output is correct: Maximum length of a query = 100 |
| 11 |
Correct |
173 ms |
568 KB |
Output is correct: Maximum length of a query = 96 |
| 12 |
Correct |
85 ms |
568 KB |
Output is correct: Maximum length of a query = 100 |
| 13 |
Correct |
168 ms |
568 KB |
Output is correct: Maximum length of a query = 101 |
