Submission #831097

#	Time	Username	Problem	Language	Result	Execution time	Memory
831097		grogu	Ancient Machine 2 (JOI23_ancient2)	C++17	0 / 100	3066 ms	1012252 KiB

ancient2

#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
**/

• Subtask 1: 0 / 100