fork download 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;
  4.  
  5. #define pb  push_back  
  6. #define ll  long long
  7. #define el  "\n"
  8. #define alla(a,n)  a+1,a+n+1
  9. #define fi first
  10. #define se second
  11. #define all(v)  v.begin(),v.end()
  12. #define fu(i,a,b)  for(ll i=a;i<=b;i++)
  13. #define fud(i,a,b)  for(ll i=a;i>=b;i--)
  14.  
  15. const ll MOD=1e9+7 ;//1234567891;
  16. const ll inf=1e18;
  17. const ll base = 311;
  18. const ll N=1e6+5;
  19. const ll N1=1e3+5;
  20. template <class T> bool mini(T &x, T y){return (x > y ? x = y, 1 : 0);}
  21. template <class T> bool maxi(T &x, T y){return (x < y ? x = y, 1 : 0);}
  22. template <class T> void add(T &x, ll y){x += y; if(x >= MOD) x -= MOD;}
  23. template <class T> void sub(T &x, T y){x -= y; if(x < 0) x += MOD;}
  24. /*v*/
  25. int dx[8] = {1, -1, 0, 0, 1, 1, -1, -1},
  26.     dy[8] = {0, 0, 1, -1, 1, -1, 1, -1};
  27.  
  28. void rtn()
  29. {
  30.     cerr<<el<<"time: "<<clock()<<"ms"<<el;
  31.     exit(0);
  32. }
  33.  
  34. ll n,k;
  35. ll a[N],nt[N];
  36.  
  37. void pre()
  38. {
  39. 	nt[0]=nt[1]=-1;
  40. 	fu(i,2,1e6)
  41. 	{
  42. 		if(nt[i]==0) for(ll j=i;j<=1e6;j+=i) nt[j]=i;
  43. 	}
  44. }
  45.  
  46. namespace sub1
  47. {
  48. 	bool checksub()
  49. 	{
  50. 		return n<=1000;
  51. 	}
  52.  
  53. 	void sol()
  54. 	{
  55. 		ll ans=0;
  56. 		vector<ll> v;
  57. 		fu(i,1,n)
  58. 		{
  59. 			ll prime=0,nonprime=0;
  60. 			fu(j,i,n)
  61. 			{
  62. 				if(nt[a[j]]==a[j]) prime++;
  63. 				else nonprime++;
  64. 				if(prime==2*nonprime)
  65. 				{
  66. 					if(maxi(ans,j-i+1))
  67. 					{
  68. 						v.clear();
  69. 						v.pb(i);
  70. 					}
  71. 					else if(ans==j-i+1)
  72. 					{
  73. 						v.pb(i);
  74. 					}
  75. 				}
  76. 			}
  77. 		}
  78. 		cout<<ans<<el;
  79. 		for(auto it:v) cout<<it<<" ";
  80. 	}
  81. }
  82.  
  83. namespace sub2
  84. {
  85. 	ll pre[N];
  86. 	ll cur[N];
  87.  
  88. 	bool check(ll x)
  89. 	{
  90. 		fu(i,1,n-x+1)
  91. 		{
  92. 			if(pre[i+x-1]-pre[i-1]==(x-x/(k+1))) return 1;
  93. 		}
  94. 		return 0;
  95. 	}
  96.  
  97. 	void sol()
  98. 	{
  99. 		fu(i,1,n) pre[i]=pre[i-1]+(nt[a[i]]==a[i]);
  100. 		ll ans=0;
  101. 		vector<ll> v;
  102. 		fu(i,1,n/(k+1)) v.pb((k+1)*i);
  103. 		ll l=0,r=v.size()-1;
  104. 		while(l<=r)
  105. 		{
  106. 			ll mid=(l+r)>>1;
  107. 			if(check(v[mid])) l=mid+1;
  108. 			else r=mid-1;
  109. 		}
  110. 		cout<<v[l-1]<<el;
  111. 		fu(i,1,n-v[l-1]+1)
  112. 		{
  113. 			if(pre[i+v[l-1]-1]-pre[i-1]==v[l-1]-v[l-1]/(k+1)) cout<<i<<" ";
  114. 		}
  115. 	}
  116. }
  117.  
  118. signed main(void)
  119. {
  120.     #define TASK  "R11AEVOD"
  121.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);srand(time(0)); 
  122.     if(fopen(TASK".inp","r"))
  123.     {
  124.         freopen(TASK".inp" ,"r",stdin) ; freopen(TASK".out" ,"w",stdout);
  125.     }
  126.  
  127.     pre();
  128.     cin>>n>>k;
  129.     fu(i,1,n) cin>>a[i];
  130.  
  131.     // if(sub1::checksub()) return sub1::sol(),0;
  132.     return sub2::sol(),0;
  133.  
  134.  
  135.     return 0;
  136. }
Runtime error #stdin #stdout 0.06s 13604KB
comments ()
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/V5o7lG
language:
C++14 (gcc 8.3)
created:
149 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!