Submission #1045454

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045454		Darren0724	Portal (BOI24_portal)	C++17	65 / 100	1701 ms	2776 KiB

Main

#pragma GCC optimize("Ofast","O3","unroll-loops")
//#pragma GCC target("avx","avx2")
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define ll long long
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define rz resize
#define pb emplace_back
#define LCBorz ios_base::sync_with_stdio(false);cin.tie(0);
#define endl '\n'
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
const int INF=2e9;
const int mod=1e9+7;
const int N=200005;
const int K=20;
const int C=2000005;
 
ll gcd(ll a,ll b){
    return abs(__gcd(a,b));
}
 
 
int32_t main(){
    LCBorz;
    int n;cin>>n;
    if(n<=2){
        cout<<-1<<endl;
        return 0;
    }
    vector<pair<int,int>> v(n),v1(n);
    for(int i=0;i<n;i++){
        int a,b;cin>>a>>b;
        v[i]={a,b};
    }
    sort(all(v));
    for(int i=1;i<n;i++){
        v[i].x-=v[0].x;
        v[i].y-=v[0].y;
    }
    ll ans=-1;
    auto solve=[&](int i,int j)->void {
        int r1=v[j].y/gcd(v[i].y,v[j].y);
        ll t=1ll*v[i].y*r1;
        int t1=t/v[j].y;
        ll x1=abs(1ll*v[i].x*r1-1ll*v[j].x*t1);
        if(x1!=0)ans=(ans==-1?x1:gcd(ans,x1));
    };
    vector<int> t;
    for(int i=1;i<n;i++){
        if(v[i].y==0){
            ans=(ans==-1?v[i].x:gcd(v[i].x,ans));
            continue;
        }
        t.push_back(i);
    }
    int sz=t.size();
    if(sz==0){
        cout<<-1<<endl;
        return 0;
    }
    for(int i=0;i<25000000;i++){
        int g1=rnd()%sz;
        int g2=rnd()%sz;
        solve(t[g1],t[g2]);
    }
    int g1=-1;
    for(int i=1;i<n;i++){
        if(v[i].y==0)continue;
        g1=(g1==-1?abs(v[i].y):gcd(g1,v[i].y));
    }
    //cout<<ans<<' '<<g1<<endl;
    cout<<(ans==-1?-1:ans*g1)<<endl;
    return 0;
}

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