Submission #1189390

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189390		peteza	Portal (BOI24_portal)	C++20	11 / 100	71 ms	13732 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, x, y;
map<int, vector<ll>> mpx, mpy;
vector<ll> xs, ys;

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n;
    for(int i=0;i<n;i++) {
        cin >> x >> y;
        xs.push_back(x); ys.push_back(y);
        mpx[x].push_back(y);
        mpy[y].push_back(x);
    }
    sort(xs.begin(), xs.end()); sort(ys.begin(), ys.end());
    for(auto &e:mpx) sort(e.second.begin(), e.second.end());
    for(auto &e:mpy) sort(e.second.begin(), e.second.end());
    ll ans = -1;
    ll cgcd = 0;
    for(auto &e:mpx) {
        for(int i=1;i<e.second.size();i++) {
            cgcd = __gcd(cgcd, e.second[i] - e.second[i-1]);
        }
    }
    if(cgcd) {
        ll cgcd2 = 0;
        for(int i=1;i<xs.size();i++) cgcd2 = __gcd(cgcd2, xs[i] - xs[i-1]);
        ans = max(ans, cgcd*cgcd2);
    }
    if(!ans) ans = -1;
    cgcd = 0;
    for(auto &e:mpy) {
        for(int i=1;i<e.second.size();i++) {
            cgcd = __gcd(cgcd, e.second[i] - e.second[i-1]);
        }
    }
    if(cgcd) {
        ll cgcd2 = 0;
        for(int i=1;i<ys.size();i++) cgcd2 = __gcd(cgcd2, ys[i] - ys[i-1]);
        ans = max(ans, cgcd*cgcd2);
    }
    if(!ans) ans = -1;
    cout << ans;
}

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