Submission #1205179

#TimeUsernameProblemLanguageResultExecution timeMemory
1205179Khalid_AlabdullatifHack (APIO25_hack)C++17
100 / 100
74 ms2052 KiB
#include "hack.h" #include <bits/stdc++.h> #define ll long long #define F first #define S second using namespace std; const ll N=1e6,mod=1e9+7,sq=27383; ll coll(vector<ll>a,vector<ll>b){ vector<ll>v; for(auto i:a) v.push_back(i); for(auto i:b) v.push_back(i); return collisions(v); } int hack(){ vector<ll> a,b; for(int i=1;i<=sq;i++) a.push_back(i); for(int i=sq*(5e8/sq);i<=1e9+sq;i+=sq) b.push_back(i); while(a.size()>1 || b.size()>1){ if(a.size()>b.size()){ vector<ll>f,s; int idx; //cout<<"F: "; for(idx=0;idx<a.size()/2;idx++){ f.push_back(a[idx]); //cout<<a[idx]<<" "; } //cout<<endl<<"S: "; for(;idx<a.size();idx++){ s.push_back(a[idx]); //cout<<a[idx]<<" "; } //cout<<endl; if(coll(s,b)) a=s; else a=f; } else{ vector<ll>f,s; int idx; //cout<<"F: "; for(idx=0;idx<b.size()/2;idx++){ f.push_back(b[idx]); //cout<<b[idx]<<" "; } //cout<<endl<<"S: "; for(;idx<b.size();idx++){ s.push_back(b[idx]); //cout<<b[idx]<<" "; } //cout<<endl; if(coll(a,f)) b=f; else b=s; } } //cout<<a[0]<<" "<<b[0]<<endl; //cout<<coll(a,b); ll m=b[0]-a[0],m1=m; set<int>prime; for (int i=2;i*i<=1e9;i++){ while(m1%i==0){ m1/=i; prime.insert(i); } } if(m1!=1) prime.insert(m1); for(auto i:prime){ while(m%i==0 && collisions({1,m/i+1})){ m/=i; } } return m; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...