Submission #1098498

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098498		_8_8_	Portal (BOI24_portal)	C++17	100 / 100	24 ms	6600 KiB

Main

#include <bits/stdc++.h>
    
using namespace std;
    
// typedef long long ll;
const int  N = 3e5 + 12, MOD = (int)1e9 + 7;
    
using ll = __int128_t;
int n, x[N], y[N];
ll G = 0;
vector<array<ll, 2>> a;
    
ll gcd (ll a, ll b) {
    if(a < 0) a *= -1;
    if(b < 0) b *= -1;
    if(!a) return b;
    if(!b) return a;
    if(a > b) swap(a, b);
    return gcd(a, b % a);
}
array<ll, 2> Gcd(array<ll, 2> c,array<ll, 2> d) {
    if(!c[0]) {
        G = gcd(G, c[1]);
        return d;
    }
    if(!d[0]) {
        G = gcd(G, d[1]);
        return c;
    }
    if(c[0] < d[0]) {
        swap(c, d);
    }
    ll col = c[0] / d[0];
    c[0] -= col * 1ll * d[0];
    c[1] -= col * 1ll * d[1];
    return Gcd(c, d);
}
void test() {
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> x[i] >> y[i];
    }
    for(int i = 2; i <= n; i++) {
        if(x[i] == x[i - 1]) {
            ll v = y[i] - y[i - 1];
            if(v < 0) v = -v;
            G = gcd(G, v);
            continue;
        }
        if(x[i] > x[i - 1]) {
            a.push_back({x[i] - x[i - 1], y[i] - y[i - 1]});
        } else {
            a.push_back({x[i - 1] - x[i], y[i - 1] - y[i]});
        }
    }
    while((int)a.size() >= 2) {
        auto i = a.back();
        a.pop_back();
        auto k = Gcd(i, a[0]);
        a[0] = k;
    }
    if(a.empty() || !a[0][0]|| !G) {
        cout << -1 << '\n';
        return;
    }
    long long res = G * a[0][0];
    cout << res << '\n';
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); 
    
    int t = 1; 
    // cin >> t;
    
    while(t--) 
        test();
    
    return 0;
}

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