Submission #1118755

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118755		YSH2020	Portal (BOI24_portal)	C++17	1 / 100	73 ms	3716 KiB

Main

//lmao not bezout lemma bash
/*
suppose there is a portal on (x1, y1), (x2, y2), and (x3, y3)
then C(x, y) = C(x+k(x2-x1), y+k(y2-y1)),
and C(x, y) = C(x+k(x3-x1), y+k(y3-y1))
C(0, 0) = C(a(x2-x1), a(y2-y1)) = C(a(x2-x1)+b(x3-x1), a(y2-y1)+b(y3-y1)). Note removal of constant terms.
thus, we try to maintain a constant x while seeing how the y will change, resulting in a vertical period.
same for horizontal period.
now we just multiply them tgt. to form a conclusion!

example: (0, 0), (4, 6), (2, 4) as below
C(4a+2b, 6a+4b)
(0, 0) -> 0
(-1, 2) -> 2
etc. shows difference in y-coords
0 <- (0, 0)
-2 <- (-2, 3)

of course, if we have a bunch of periods, (like period of 2 period of 3 etc. just take gcd of them all)
very mathematical approach!
so now we translate into code!

an obvious claim: if there are less than 3, you can colour infinitely.
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
int gcd(int a, int b) {
    if (a < 0) a *= -1;
    if (b < 0) b *= -1;
    if (b > a) swap(a, b);
    if (b == 0) return a;
    return gcd(b, a%b);
}

pair<int, int> get_period(int change_x1, int change_x2, int change_y1, int change_y2) {
    int tmp = gcd(change_x1, change_x2);
    int period_x;
    if (tmp == 0) period_x = 0;
    else {
        int a = -change_x2/tmp;
        int b = change_x1/tmp;
        period_x = change_y1*a+change_y2*b;
    }
    tmp = gcd(change_y1, change_y2);
    int period_y;
    if (tmp == 0) period_y = 0;
    else {
        int a = -change_y2/tmp;
        int b = change_y1/tmp;
        period_y = change_x1*a+change_x2*b;
    }
    return {period_x, period_y};
}

signed main() {
    int n; cin >> n;
    if (n < 3) {cout << -1; return 0;}
    int start_x1, start_y1; cin >> start_x1 >> start_y1;
    int start_x2, start_y2; cin >> start_x2 >> start_y2;
    vector<pair<int, int>> periods;
    for (int i = 0; i < n-2; i++) {
        int x, y; cin >> x >> y;
        periods.push_back(get_period(abs(start_x2-start_x1), abs(x-start_x1), 
        abs(start_y2-start_y1), abs(y-start_y1)));
    }
    int ans_x = 0;
    int ans_y = 0;
    for (int i = 0; i < n-2; i++) {
        //note one fun property of the gcd code: you can gcd 0 with any integer to get that integer.
        ans_x = gcd(ans_x, periods[i].first);
        ans_y = gcd(ans_y, periods[i].second);
    }
    if (ans_x == 0 or ans_y == 0) cout << -1;
    else {
        long long ans = ans_x*ans_y;
        cout << ans;
    }
}

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