Submission #1203630

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203630		BigBadBully	Portal (BOI24_portal)	C++20	100 / 100	38 ms	2120 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
using namespace std;
int mcd(int a,int b)
{
    if (a>b)swap(a,b);
    if (a==0)return b;
    a = abs(a),b = abs(b);
    return __gcd(a,b);
}

int exg(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int x1, y1;
    int d = exg(b, a % b, x1, y1);
    x = y1;
    y = x1 - y1 * (a / b);
    return d;
}

signed main()
{
    int n;
    cin >> n;
    vector<pii> v(n);
    for (int i = 0; i < n ;i++)
        cin >> v[i].ff >> v[i].ss;
    for (int i = n-1; i >= 0; i--)
        v[i].ff-=v[0].ff,v[i].ss-=v[0].ss;
    int x = (v[1].ss==0?v[1].ff:0), y = v[1].ss,px = v[1].ff,py = v[1].ss,up = v[1].ss;
    for (int i = 2; i < n; i++)
    {
        int add = 0;
        if (v[i].ss == 0)
            add = v[i].ff;
        else if (py!=0)
        {
            int lc = v[i].ss*py/mcd(v[i].ss,py);   
            int c1 = lc/py;
            int c2 = lc/v[i].ss;
            add = c2*v[i].ff - c1*px;
        }
        x = mcd(x,add);
        int k1,k2;
        y = exg(py,v[i].ss,k1,k2);
        py = y;
        px = k1*px + k2*v[i].ff;
        if(x)
        {
            int dum = 1000;
            while(dum*x < abs(px))
                dum*=2;
            px+=dum*x;
            px%=x;
        }
    }
    if (x*y == 0)
        cout << -1;
    else
        cout << abs(x*y);
    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