Submission #1098470

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098470		_8_8_	Portal (BOI24_portal)	C++17	0 / 100	2036 ms	604 KiB

Main

#include <bits/stdc++.h>
    
using namespace std;
    
typedef long long ll;
const int  N = 3e5 + 12, MOD = (int)1e9 + 7;

int n, x[N], y[N];
ll G = 0;
vector<array<ll, 2>> 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]) {
            G = gcd(G, y[i] - y[i - 1]);
            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 j = a.back();
        auto k = Gcd(i, j);
        a.push_back(k);
    }

    cout << G * 1ll * (a[0][0]) << '\n';
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); 

    int t = 1; 
    // cin >> t;

    while(t--) 
        test();

    return 0;
}

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