Submission #1049466

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1049466	2024-08-08T19:14:17 Z	shenfe1	Portal (BOI24_portal)	C++17	Compilation error	0 ms	0 KB

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 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];
                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){
        // cerr<<sz(vec)<<" "<<vec[0].F<<" "<<vec[0].S<<" "<<vec[1].F<<" "<<vec[1].S<<"\n";
        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==make_pair(0ll,0ll))cout<<"1WTF\n";
        // if(res.S==make_pair(0ll,0ll))cout<<"WTF\n";
        // cout<<res.F.F<<" "<<res.F.S<<" "<<res.S.F<<" "<<res.S.S<<"\n";
        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

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")
      | 
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:84,
                 from Main.cpp:1:
/usr/include/c++/10/numeric: In instantiation of 'constexpr std::common_type_t<_Mn, _Nn> std::gcd(_Mn, _Nn) [with _Mn = __int128; _Nn = __int128; std::common_type_t<_Mn, _Nn> = __int128]':
Main.cpp:66:26:   required from here
/usr/include/c++/10/numeric:133:21: error: static assertion failed: gcd arguments are integers
  133 |       static_assert(is_integral_v<_Mn>, "gcd arguments are integers");
      |                     ^~~~~~~~~~~~~~~~~~
/usr/include/c++/10/numeric:134:21: error: static assertion failed: gcd arguments are integers
  134 |       static_assert(is_integral_v<_Nn>, "gcd arguments are integers");
      |                     ^~~~~~~~~~~~~~~~~~
/usr/include/c++/10/numeric: In instantiation of 'constexpr std::common_type_t<_Mn, _Nn> std::__detail::__gcd(_Mn, _Nn) [with _Mn = __int128; _Nn = __int128; std::common_type_t<_Mn, _Nn> = __int128]':
/usr/include/c++/10/numeric:139:29:   required from 'constexpr std::common_type_t<_Mn, _Nn> std::gcd(_Mn, _Nn) [with _Mn = __int128; _Nn = __int128; std::common_type_t<_Mn, _Nn> = __int128]'
Main.cpp:66:26:   required from here
/usr/include/c++/10/numeric:104:49: error: use of deleted function 'void std::__detail::__abs_integral(bool)'
  104 |       return __m == 0 ? __detail::__abs_integral(__n)
      |                         ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
/usr/include/c++/10/numeric:98:8: note: declared here
   98 |   void __abs_integral(bool) = delete;
      |        ^~~~~~~~~~~~~~
/usr/include/c++/10/numeric:105:39: error: use of deleted function 'void std::__detail::__abs_integral(bool)'
  105 |  : __n == 0 ? __detail::__abs_integral(__m)
      |               ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
/usr/include/c++/10/numeric:98:8: note: declared here
   98 |   void __abs_integral(bool) = delete;
      |        ^~~~~~~~~~~~~~