#include "ancient2.h"
#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include <bits/stdc++.h>
#define ld double
#define ll int
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define eb emplace_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;}
#define si(a) (ll)(a.size())
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rnd(ll l,ll r){
return uniform_int_distribution<ll>(l,r)(rng);
}
#define mod 1000000007
ll add(ll x,ll y){
x+=y;
if(x<0){
x%=mod;
x+=mod;
}else{
if(x>=mod) x%=mod;
}
return x;
}
ll mul(ll a,ll b){
long long ans = (((long long)a)*((long long)b))%mod;
if(ans<0) ans+=mod;
return ans;
}
ll po(ll x,ll y){
if(y==0) return 1LL;
ll ans = po(x,y/2);
ans = mul(ans,ans);
if(y&1) ans = mul(ans,x);
return ans;
}
ll inv(ll x){return po(x,mod-2);}
#define maxn 1005
ll n;
ll a[maxn];
ll dp[maxn];
pll opt[maxn];
ll p;
ll hsh[maxn];
ll powe[maxn];
ll get(ll l,ll r){
return add(hsh[r],-mul(powe[r-l+1],hsh[l-1]));
}
ll ls[maxn],rs[maxn];
ll tsz = 0;
bool di = 0;
void add(vector<ll> &a,vector<ll> &b,ll y,ll f){
ll poc = si(a);
for(ll i = 0;i<y;i++){
if(f==0){
a.pb(poc+i+1);
b.pb(poc+i);
}else{
a.pb(poc+i);
b.pb(poc+i+1);
}
}
if(b.back()>a.back()) b.back() = poc;
else a.back() = poc;
}
ll x = 500,y = 3;
ll f(ll dx,ll dy){
for(ll i = 0;i<=n;i++){
if(i%x==dx&&i%y==dy) return i;
}
return -69;
}
string add(string s,ll i,ll k){
while(i--){
if(k==0) s+="0";
else s+="1";
}
return s;
}
string Solve(int N) {
powe[0] = 1;
p = rnd(2,mod-1);
for(ll i = 1;i<maxn;i++) powe[i] = mul(powe[i-1],p);
n = N;
dp[0] = 0;
opt[0] = {-1,-1};
vector<ll> bpoc,cpoc;
vector<ll> d;
ll last = 0;
ll sum = 0;
while(1){
vector<ll> b = bpoc;
vector<ll> c = cpoc;
add(b,c,500,0);
//dbg(si(b));
//cer(b);
//cer(c);
ll poc = si(bpoc);
ll dx = Query(si(b),b,c)-poc;
if(dx<0){
last = 0;
break;
}
//dbg(dx);
if(dx==0&&si(d)&&d.back()==0) break;
sum+=dx;
d.pb(dx);
bpoc.pb(poc+1); bpoc.pb(poc+1);
cpoc.pb(poc); cpoc.pb(poc+2);
}
vector<ll> d1;
bpoc.clear();
cpoc.clear();
while(1){
vector<ll> b = bpoc;
vector<ll> c = cpoc;
add(b,c,500,1);
//dbg(si(b));
ll poc = si(bpoc);
ll dx = Query(si(b),b,c)-poc;
if(dx<0){
last = 1;
break;
}
if(dx==0&&si(d1)&&d1.back()==0) break;
sum+=dx;
d1.pb(dx);
cpoc.pb(poc+1); cpoc.pb(poc+1);
bpoc.pb(poc); bpoc.pb(poc+2);
}
if(sum==500){
ll i = 0;
while(1){
vector<ll> b = bpoc;
vector<ll> c = cpoc;
add(b,c,3,0);
//dbg(si(b));
//cer(b);
//cer(c);
ll poc = si(bpoc);
ll dx = Query(si(b),b,c)-poc;
if(dx<0){
last = 0;
break;
}
d[i] = f(d[i],dx);
i++;
bpoc.pb(poc+1); bpoc.pb(poc+1);
cpoc.pb(poc); cpoc.pb(poc+2);
}
i = 0;
vector<ll> d1;
bpoc.clear();
cpoc.clear();
while(1){
vector<ll> b = bpoc;
vector<ll> c = cpoc;
add(b,c,3,1);
ll poc = si(bpoc);
ll dx = Query(si(b),b,c)-poc;
if(dx<0){
last = 1;
break;
}
d1[i] = f(d1[i],dx);
cpoc.pb(poc+1); cpoc.pb(poc+1);
bpoc.pb(poc); bpoc.pb(poc+2);
}
}
if(d.back()==0) d.popb();
if(d1.back()==0) d1.popb();
reverse(all(d));
reverse(all(d1));
for(ll i = si(d)-1;i>0;i--){
d[i] = d[i] - d[i-1];
}
for(ll i = si(d1)-1;i>0;i--){
d1[i] = d1[i] - d1[i-1];
}
cer(d);
cer(d1);
string ans;
ll i = 0,j = 0;
while(i<si(d)||j<si(d1)){
if(i==si(d)){
while(j<si(d1)){
ans = add(ans,d1[j],1);
j++;
}
}else if(j==si(d1)){
while(i<si(d)){
ans = add(ans,d[i],0);
i++;
}
}else{
if(last==1){
ans = add(ans,d1[j],1);
j++;
}else{
ans = add(ans,d[i],0);
i++;
}
last^=1;
}
}
dbg(ans);
reverse(all(ans));
return ans;
}
/**
3
110
10
1001101011
10
1010011011
**/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3066 ms |
1012252 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
