Submission #1098489

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098489		_8_8_	Portal (BOI24_portal)	C++17	1 / 100	17 ms	3444 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) {
	while (b) {
		a %= b;
		swap (a, b);
	}
	return 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;
    }
    // assert(G);
    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: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 29
• Subtask 5: 0 / 15
• Subtask 6: 0 / 35