Submission #1206567

#TimeUsernameProblemLanguageResultExecution timeMemory
1206567StefanSebezHack (APIO25_hack)C++20
25 / 100
301 ms2756 KiB
#include "hack.h" #include <vector> #include<bits/stdc++.h> using namespace std; #define fi first #define se second #define pb push_back #define ll long long #define ld long double /*const int N=1e6+10; vector<int>dvs[N+5];*/ const int M=22900; const ll inf=4e17; mt19937_64 rng(time(0)); ll Sredi(ll x){ ll res=x; vector<ll>p; for(int i=2;i<=sqrt(x);i++){ while(x%i==0){x/=i;p.pb(i);} } p.pb(x); for(auto i:p){ res/=i; if(collisions({1,res+1})==0) res*=i; } return res; } vector<ll> Resi(vector<ll>a){ int n=a.size(); vector<ll>b,c; for(int i=0;i<n;i++){ if(i<=(n-1)/2) b.pb(a[i]); else c.pb(a[i]); } if(collisions(b)) return Resi(b); if(collisions(c)) return Resi(c); return a; } int hack(){ /*for(int i=1;i<=N;i++) dvs[i].clear(); for(int i=1;i<=N;i++) for(int j=i;j<=N;j+=i) dvs[j].pb(i); int x=0; for(int i=N;i>=1&&x==0;i--){ if(collisions({1,i})==1){ x=i-1; } } int res=x; for(auto i:dvs[x]){ if(collisions({1,i+1})==1) res=min(res,i); } return res;*/ vector<ll>a; /*int ct=0; while(++ct){ a.clear(); for(int i=1;i<=M;i++) a.pb(rng()%inf+1); if(collisions(a)) break; }*/ for(int i=1;i<=M/3;i++) a.pb(rng()%inf+1); while(!collisions(a)){ int n=a.size(); for(int i=1;2*i<=n;i++) a.pb(rng()%inf+1); } a=Resi(a); int n=a.size(); cerr<<n<<endl; int Mid=(n-1)/2; int l=Mid+1,r=n-1,ind,ind1; while(l<r){ int mid=l+r>>1; //printf("%i %i %i\n",l,mid,r); vector<ll>temp; for(int i=0;i<=Mid;i++) temp.pb(a[i]); for(int i=l;i<=mid;i++) temp.pb(a[i]); if(collisions(temp)) r=mid; else l=mid+1; } ind=l; /*l=0,r=Mid; while(l<r){ int mid=l+r>>1; vector<ll>temp={a[ind]}; for(int i=l;i<=mid;i++) temp.pb(a[i]); if(collisions(temp)) r=mid; else l=mid+1; }*/ ll res=0; for(int i=0;i<=Mid;i++){ if(collisions({a[i],a[ind]})){res=abs(a[i]-a[ind]);break;} } //ind1=l; //res=abs(a[ind]-a[ind1]); //cerr<<res<<endl; res=Sredi(res); return res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...