제출 #1200832

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1200832		Mighilon	마술쇼 (APIO24_show)	C++20	100 / 100	3 ms	376 KiB

Alice

#include <bits/stdc++.h>
using namespace std;
 
#ifdef DEBUG
#include "../Library/debug.h"
#else
#include "Alice.h"
#define dbg(x...)
#endif

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl; 
 
#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 (inBobt i = (b) - 1; i >= (a); --i)
#define F0Rd(i, a) for (int i = (a) - 1; i >= 0; --i)
#define trav(a, x) for (auto& a : x)
#define f first 
#define s second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) x.begin(), x.end()
 
const char nl = '\n';
const int INF = 1e9;
const ll MOD = 998244353;
const int mxN = 3e5+5;

#ifdef DEBUG
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll N, M;
ll setN(ll x){
    N=x;
    return M=uniform_int_distribution<ll>(int64_t(1e18),int64_t(1e18))(rng);
}
#endif
void __print(__int128_t x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x>9) __print(x/10);
    putchar(x%10 + '0');
}

vpi Alice(){
    int n = 5000;
    ll x = setN(n);
    vpi res;
    FOR(i,2,n+1){
        res.pb({(x%(i-1))+1,i});
    }
    return res;
}

void print(__int128_t x){
    if(x<0){
        putchar('-');
        x*=-1;
    }
    if(x>9)print(x/10);
    putchar(x%10 + '0');
}

namespace BOB{
    __int128_t ex_gcd(__int128_t a,__int128_t b,__int128_t& x,__int128_t& y){
        if(b==0){
            x=1;
            b=0;
            return a;
        }
        __int128_t x1=0,y1=0;
        __int128_t d=ex_gcd(b,a%b,x1,y1);
        x=y1;
        y=x1-a/b*y1;
        return d;
    }

    ll mul(ll a, ll b, ll m){
        ll s=1;
        if(b<0)s=-1,b*=-1;
        ll ans=0;
        while(b>0){
            if(b%2==1)ans=(ans+s*a)%m;
            b>>=1;
            a=(a+a)%m;
        }
        return ans;
    }
    ll Bob(vpi v){
        ll num[19];
        num[0]=1;
        F0R(i,18) num[i+1]=num[i]*10;
        auto check=[&](ll a, ll b){
            int x=0,y=0;
            F0R(i,19)if(a<num[i]){
                x=i;
                break;
            }
            if(a&&!x) x=19;
            if(b&&!y) y=19;
            F0R(i,19)if(b<num[i]){
                y=i;
                break;
            }
            return (x+y)<=20;
        };
        __int128_t res=0;
        __int128_t m=1;
        trav(i,v){
            i.f-=1;
            i.s-=1;
            __int128_t x, y,d;
            d=ex_gcd(m,i.s,x,y);
            assert((res-i.f)%d==0);
            // if(!check(m,i.s)){
            if(m > 1e18){
                // dbg(m,i.s)
                return res;
            }
            // print(m);
            // dbg('-',res);
            res = res+(i.f-res)/d*x%(i.s/d)*m;
            // res = res + mul(mul((i.f-res)/d, x,(i.s/d)),m,(m/d*i.s));
            m = m/d*i.s;
            res%=m;
            if(res<0)res+=m;
        }
        return res;
    }
    
}


#ifdef DEBUG
int main(){
    auto gen=[&](ll a, ll b){
        return uniform_int_distribution(a,b)(rng);
    };
    int cnt=0;
    while(1){
        vpi edges = Alice();
        shuffle(all(edges),rng);
        int rem=gen(1,N/2);
        edges.erase(edges.end()-rem, edges.end());
        ll ans = BOB::Bob(edges);
        dbg(++cnt,ans, M);
        if(ans != M){
            dbg(N,M,ans);
            return 0;
        }
    }
    return 1;
}
#endif

Bob

#include <bits/stdc++.h>
using namespace std;
 
#ifdef DEBUG
#include "../Library/debug.h"
#else
#include "Bob.h"
#define dbg(x...)
#endif
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl; 
 
#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 trav(a, x) for (auto& a : x)
#define f first 
#define s second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) x.begin(), x.end()
 
const char nl = '\n';
const int INF = 1e9;
const int MOD = 1e9 + 7;

__int128_t ex_gcd(__int128_t a,__int128_t b,__int128_t& x,__int128_t& y){
    if(b==0){
        x=1;
        b=0;
        return a;
    }
    __int128_t x1=0,y1=0;
    __int128_t d=ex_gcd(b,a%b,x1,y1);
    x=y1;
    y=x1-a/b*y1;
    return d;
}

ll mul(ll a, ll b, ll m){
    ll s=1;
    if(b<0)s=-1,b*=-1;
    ll ans=0;
    while(b>0){
        if(b%2==1)ans=(ans+s*a)%m;
        b>>=1;
        a=(a+a)%m;
    }
    return ans;
}
ll Bob(vpi v){
    ll num[19];
    num[0]=1;
    F0R(i,18) num[i+1]=num[i]*10;
    auto check=[&](ll a, ll b){
        int x=0,y=0;
        F0R(i,19)if(a<num[i]){
            x=i;
            break;
        }
        if(a&&!x) x=19;
        if(b&&!y) y=19;
        F0R(i,19)if(b<num[i]){
            y=i;
            break;
        }
        return (x+y)<=20;
    };
    __int128_t res=0;
    __int128_t m=1;
    trav(i,v){
        i.f-=1;
        i.s-=1;
        __int128_t x, y,d;
        d=ex_gcd(m,i.s,x,y);
        assert((res-i.f)%d==0);
        // if(!check(m,i.s)){
        if(m > 1e18){
            // dbg(m,i.s)
            return res;
        }
        // print(m);
        // dbg('-',res);
        res = res+(i.f-res)/d*x%(i.s/d)*m;
        // res = res + mul(mul((i.f-res)/d, x,(i.s/d)),m,(m/d*i.s));
        m = m/d*i.s;
        res%=m;
        if(res<0)res+=m;
    }
    return res;
}

• Subtask 1: 5 / 5
• Subtask 2: 30 / 30
• Subtask 3: 65 / 65