제출 #1166410

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1166410		Math4Life2020	Portal (BOI24_portal)	C++20	11 / 100	32 ms	4832 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = __int128; using pii = pair<ll,ll>;

ll gcd2(ll a, ll b) {
    if (a==0 || b==0) {
        return max(labs(a),labs(b));
    }
    return gcd(labs(a),labs(b));
}

ll cpr(pii p1, pii p2) {
    return (p1.first*p2.second-p2.first*p1.second);
}

inline ll fmod(ll x, ll MOD) {
    return (x+MOD*(2-x/MOD))%MOD;
}

inline pii fmod(pii p0, ll MOD) {
    return {fmod(p0.first,MOD),fmod(p0.second,MOD)};
}

ll inv(ll x, ll MOD) {
    assert(MOD!=0);
    if (MOD<0) {
        MOD=-MOD;
    }
    x = fmod(x,MOD);
    array<ll,3> a = {x,1,0};
    array<ll,3> b = {MOD,0,1};
    while (b[0]!=1) {
        if (a[0]>b[0]) {
            swap(a,b);
        } else {
            ll k = b[0]/a[0];
            for (ll i=0;i<3;i++) {
                b[i]-=k*a[i];
            }
        }
    }
    return fmod(b[1],MOD);
}

pii fix(pii p1, pii p2) { //assuming cpr = 0, adjust both
    assert(cpr(p1,p2)==0);
    if (p1.first==0 && p1.second==0) {
        return p2;
    }
    if (p2.first==0 && p2.second==0) {
        return p1;
    }
    if (p1.first==0 && p2.first==0) {
        return {0LL,gcd2(p1.second,p2.second)};
    }
    if (p1.second==0 && p2.second==0) {
        return {gcd2(p1.first,p2.first),0LL};
    }
    ll a = gcd2(p1.first,p2.first);
    return {a,(p1.second*a)/p1.first};
}

ll ans = 0;
ll nvec = 0;
pii p0,p1;

void flip() {
    if (nvec==2) {
        swap(p0,p1);
    }
}

void anl() {
    if (ans==-1) {
        if (nvec==2) {
            if (cpr(p1,p0)==0) {
                p1 = fix(p1,p0);
                nvec=1;
            }
        }
        return;
    }
    if (nvec==0) {
        return;
    }
    if (nvec==1) {
        p0 = fmod(p0,ans);
        if (p0.first==0 && p0.second==0) {
            nvec = 0;
        }
        return;
    }
    if (nvec==2) {
        p0 = fmod(p0,ans);
        if (p0.first==0 && p0.second==0) {
            nvec = 1;
            swap(p0,p1);
            anl();
            return;
        }
        p1 = fmod(p1,ans);
        if (p1.first==0 && p1.second==0) {
            nvec = 1;
            anl();
            return;
        }
        if (cpr(p1,p0)==0) {
            p1 = fix(p1,p0);
            nvec = 1;
            anl();
            return;
        }
        assert(ans%labs(cpr(p1,p0))==0);
        if (labs(cpr(p1,p0))<ans) {
            ans = labs(cpr(p1,p0));
            anl();
        }
        return;
    }
}

void fz0(pii p2) {
    if (nvec==0) {
        p0 = p2; return;
    }
    if (nvec==1) {
        if (cpr(p0,p2)==0) {
            p0 = fix(p0,p2);
            return;
        } else {
            p1 = p2;
            nvec = 2;
            if (ans==-1) {
                ans = labs(cpr(p0,p1));
            } else {
                ans = gcd2(labs(cpr(p0,p1)),ans);
            }
            return;
        }
    }
    if (nvec==2) {
        if (labs(cpr(p0,p2))%ans!=0) {
            ans = gcd2(cpr(p0,p2),ans);
            p1 = p2;
            return;
        }
        if (labs(cpr(p1,p2))%ans!=0) {
            ans = gcd2(cpr(p1,p2),ans);
            p0 = p2;
            return;
        }
    }
}

void fz(pii p2) {
    anl();
    if (ans!=-1) {
        p2 = fmod(p2,ans);
    }
    if (p2.first==0 && p2.second==0) {
        return;
    }
    fz0(p2);
    anl();
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    long long N; cin >> N;
    if (N<=2) {
        cout << "-1\n";
        exit(0);
    }
    long long x0,y0; cin >> x0 >> y0;
    vector<pii> v0;
    for (ll i=0;i<(N-1);i++) {
        long long x1,y1; cin >> x1 >> y1;
        v0.push_back({x1-x0,y1-y0});
    }
    ll ansS = 0;
    for (ll i=1;i<(N-1);i++) {
        ansS = gcd2(ansS,cpr(v0[0],v0[i]));
    }
    if (ansS == 0) {
        cout << "-1\n"; exit(0);
    }
    ans = ansS;
    for (pii p2: v0) {
        while(1) {
            ll ansc = ans;
            pii p0c = p0; pii p1c = p1;
            fz(p2);
            flip();
            fz(p2);
            fz(p1);
            flip();
            fz(p1);
            fz(p0);
            flip();
            fz(p0);
            ll ansc2 = ans;
            assert(ansc%ansc2==0);
            if (ansc2==ansc) {
                break;
            }
        }
    }
    cout << (long long) ans << "\n";
}

• Subtask 1: 1 / 1
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 29
• Subtask 5: 0 / 15
• Subtask 6: 0 / 35