#include "ancient2.h"
#include<bits/stdc++.h>
using namespace std;
#define in insert
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second
//#define int long long
typedef long long ll;
typedef vector<int> vi;
typedef set<int> si;
typedef multiset<int> msi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
int n;
vector<int> a, b;
string ask, ans;
void solve(int l, int r) {
if(l > r) return;
if(l == r) {
int m = a.size();
a.pb(m + 1); a.pb(m + 1);
b.pb(m); b.pb(m + 1);
if(Query(m, a, b) == m + 1) ans.back() = '0';
else ans.back() = '1';
for(int i = 0; i < 2; i++) {
a.pop_back();
b.pop_back();
}
return;
}
int m = (l + r) / 2;
vector<int> _a = a, _b = b;
for(int i = l; i <= m; i++) {
int sz = _a.size();
_a.pb(sz + 2);
_b.pb(sz + 1);
for(int j = 0; j < 2; j++) {
_a.pb(sz + j + 1);
_b.pb(sz + j + 1);
}
int l = Query((int)_a.size(), _a, _b);
if(l == sz + 2) ans[i] = '0';
else ans[i] = '1';
for(int j = 0; j < 3; j++) {
_a.pop_back();
_b.pop_back();
}
_a.pb(sz + 1);
_b.pb(sz + 1);
}
int ls = -1;
for(int i = l + 1; i <= m; i++) {
int sz = (int)a.size();
if(ans[i] != ans[i - 1]) {
if(ans[i] == '0') {
b.pb(sz);
a.pb(sz + 1);
} else {
a.pb(sz);
b.pb(sz + 1);
}
ls = i;
i++;
}
}
if(ls == m) {
solve(m + 1, r);
return;
}
_a = a;
_b = b;
int sz = (int)a.size();
if(ans[m] == '0') {
_a.pb(sz);
_b.pb(sz + 1);
} else {
_b.pb(sz);
_a.pb(sz + 1);
}
while(_a.size() < 504) {
int pp = (int)_a.size();
_a.pb(pp + 1);
_b.pb(pp + 1);
}
_a.pb(504);
_b.pb(504);
assert((int)_a.size() == 505);
int q = Query((int)a.size(), a, b);
if(q == sz) {
for(int i = m + 1; i <= r; i++) {
ans[i] = ans[m];
}
return;
}
int len = q - sz - 1;
if(ans[m] == '0') {
a.pb(sz);
b.pb(sz + 1);
} else {
b.pb(sz);
a.pb(sz + 1);
}
for(int i = m + 1; i <= r - len - 1; i++) {
ans[i] = ans[m];
}
ans[r - len] = ans[m] ^ '0' ^ '1';
solve(r - len + 1, r);
}
string Solve(int _n) {
n = _n;
ans = string(n, '0');
solve(0, n - 1);
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
332 KB |
Wrong Answer [6] |
| 2 |
Halted |
0 ms |
0 KB |
- |
