Submission #1049477

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049477		shenfe1	Portal (BOI24_portal)	C++17	100 / 100	46 ms	13964 KiB

Main

#include <bits/stdc++.h>

#pragma optimize("Ofast")
#pragma target("avx2")

using namespace std;

#define ll long long
#define ld long double
#define pb push_back
#define pii pair<int,int>
#define all(v) v.begin(),v.end()
#define F first
#define S second
#define mem(a,i) memset(a,i,sizeof(a))
#define sz(s) (int)s.size()
#define ppb pop_back
#define lb lower_bound
#define ub upper_bound
#define in insert
#define int ll

const int MAX=3e5+15;
const ll inf=1e18+1;
const int mod=998244353;
const int mod1=1e9+9;

int dx[8]={1,0,-1,0,1,-1,-1,1};
int dy[8]={0,1,0,-1,1,-1,1,-1};

int binpow(int a,int n){
    if(!n)return 1;
    if(n%2==1)return a*binpow(a,n-1)%mod;
    int k=binpow(a,n/2);
    return k*k%mod;
}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n;

pair<pair<int,__int128>,pair<int,__int128>> gcd(pair<int,__int128> a,pair<int,__int128> b){
    if(a.F==0||b.F==0)return {a,b};
    if(a.F<b.F)swap(a,b);
    int c=a.F/b.F;
    a.F%=b.F;
    a.S-=b.S*c;
    return gcd(b,a);
}

int x[MAX],y[MAX];

void cr(__int128 a){
    vector<int> x;
    if(a==0)cerr<<0;
    while(a>0)x.pb(a%10);
    reverse(all(x));
    for(int f:x)cerr<<f;
    cerr<<"\n";
}

__int128 gcd(__int128 a,__int128 b){
    // cr(a),cr(b);
    if(b<0)b*=-1;
    if(a<0)a*=-1;
    if(a==0)return b;
    if(b==0)return a;
    if(a<b)swap(a,b);
    return gcd(b,a%b);
}

void solve(){
    cin>>n;
    if(n<=2){
        cout<<-1<<"\n";
        return;
    }
    for(int i=1;i<=n;i++)cin>>x[i]>>y[i];
    __int128 g=0;
    set<pair<int,__int128>> vec;
    for(int i=2;i<=n;i++){
        if(x[i]==x[1]){
            if(y[i]!=y[1]){
                __int128 f=y[i]-y[1];
                // cr(g),cr(f);
                g=gcd(g ,f);
            }
        }
        else{
            if(x[i]-x[1]>0)vec.insert({x[i]-x[1],y[i]-y[1]});
            else vec.insert({x[1]-x[i],y[1]-y[i]});
        }
    }
    while(sz(vec)>=2){
        pair<int,__int128> a=*vec.begin();
        vec.erase(vec.begin());
        pair<int,__int128> b=*vec.begin();
        vec.erase(vec.begin());
        pair<pair<int,__int128>,pair<int,__int128>> res=gcd(a,b);
        if(res.F.F==0){
            if(res.F.S!=0){
                g=gcd(g,res.F.S);
            }
        }
        else vec.insert(res.F);
        if(res.S.F==0){
            if(res.S.S!=0){
                g=gcd(g,res.S.S);
            }
        }
        else vec.insert(res.S);
    }
    if(vec.empty()||g==0)cout<<-1<<"\n";
    else{
        // cout<<g<<" "<<vec.begin()->F<<" "<<vec.begin()->S<<"\n";
        int G=g;
        cout<<G*vec.begin()->F<<"\n";
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
}

Compilation message (stderr)

Main.cpp:3: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    3 | #pragma optimize("Ofast")
      | 
Main.cpp:4: warning: ignoring '#pragma target ' [-Wunknown-pragmas]
    4 | #pragma target("avx2")
      |

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