/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 29ms 9.129 MiB
#2 Accepted 47ms 9.348 MiB
#3 Accepted 62ms 9.188 MiB
#4 Accepted 278ms 9.332 MiB
#5 Accepted 280ms 9.336 MiB
#6 Accepted 298ms 9.34 MiB
#7 Accepted 29ms 9.312 MiB
#8 Accepted 81ms 9.34 MiB
#9 Accepted 63ms 9.152 MiB
#10 Accepted 68ms 9.234 MiB
#11 Accepted 88ms 9.473 MiB
#12 Accepted 91ms 9.551 MiB
#13 Accepted 260ms 9.344 MiB
#14 Accepted 234ms 9.215 MiB
#15 Accepted 294ms 9.344 MiB
#16 Accepted 71ms 9.344 MiB
#17 Accepted 294ms 9.34 MiB
#18 Accepted 74ms 9.359 MiB
#19 Accepted 87ms 9.336 MiB
#20 Accepted 39ms 9.34 MiB
#21 Accepted 90ms 9.352 MiB
#22 Accepted 83ms 9.352 MiB
#23 Accepted 296ms 9.344 MiB
#24 Accepted 270ms 9.34 MiB
#25 Accepted 292ms 9.121 MiB
#26 Accepted 286ms 9.148 MiB
#27 Accepted 293ms 9.332 MiB
#28 Accepted 38ms 9.125 MiB
#29 Accepted 42ms 9.324 MiB
#30 Accepted 34ms 9.125 MiB

Code

#include<bits/stdc++.h>
using namespace std;
const long long M=5e5+10,MOD=998244353;
typedef long long ll;
#define debug(x) cout<<x<<endl
int p[M];
int nxt[M];
int pr[M];
int vis[M][2];
void precal(){
	for(int i=1;i<M;i++)p[i]=i,nxt[i]=M;
	for(int i=2;i<M;i++){
		for(int j=i+i;j<M;j+=i)p[j]=j/i;
	}
	for(int i=2;i<M;i++){
		if(p[i]==i)pr[i]=i;
		pr[i]=max(pr[i],pr[i-1]);
		
	}
	for(int i=M-10;i>=2;i--){
		if(p[i]==i)nxt[i]=i;
		nxt[i]=min(nxt[i],nxt[i+1]);
	}
	int cnt=0;
	//for(int i=2;i<=3e5;i++)cnt+=(p[i]==i);
	//cout<<cnt*2*100*10<<endl;
	


}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    precal();
    int t=1;
    cin>>t;
    while(t--){
    	int n,m,k;
    	cin>>n>>m>>k;
    	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
    	pq.push({n,k});
    	int ans=2;
    	//vis[n][k%2]=1;
    	while(!pq.empty()){
    		int cur_n=pq.top().first;
    		int cur_k=pq.top().second;
    		//cout<<cur_n<<" "<<cur_k<<endl;
    		pq.pop();
    		for(int i=1;i<=m;i++){
    			int x=cur_n+i;
    			int y=cur_n-i;
    			if(cur_k==1){
    				ans=max(ans,p[x]);
    				if(y>1)ans=max(ans,p[y]);
    			}
    			else{
    				if(!vis[p[x]][(cur_k-1)%2]){
    					pq.push({p[x],cur_k-1});
    					vis[p[x]][(cur_k-1)%2]=1;
    				}
    				if(y>1 && !vis[p[y]][(cur_k-1)%2]){
    					pq.push({p[y],cur_k-1});
    					vis[p[y]][(cur_k-1)%2]=1;
    				}
    			}
    		}
    		if(cur_n==p[cur_n]){
    			int samna=nxt[cur_n+1];
    			int picha=pr[cur_n-1];
    			if(samna-cur_n<=m){
    				if(cur_k & 1)ans=max(samna,ans);
    				else ans=max(ans,cur_n);
    			}
    			if(picha>1 && cur_n-picha<=m){
    				if(cur_k & 1)ans=max(picha,ans);
    				else ans=max(ans,cur_n);
    			}
    		}
    		
    	}
    	cout<<ans<<"\n";
    	int limit=4e5;
    	for(int i=2;i<=limit;i++){
    		vis[i][0]=vis[i][1]=0;
    	}
    }
    return 0;
 
}

Information

Submit By
Type
Submission
Problem
P1146 Yet Another Battle Between Roy and Hridoy!
Language
C++17 (G++ 13.2.0)
Submit At
2024-12-03 13:56:47
Judged At
2024-12-17 11:25:55
Judged By
Score
100
Total Time
298ms
Peak Memory
9.551 MiB