fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. #define endl '\n'
  5. const double PI = acos(-1);
  6. const double dError = -1e-9;
  7. const int mod = 1e9+7;
  8. const int N = 1e5+5;
  9. bool isPrime[N];
  10. int dp[N];
  11. vector<int> primes;
  12. vector<int> idx(N+1);
  13. int n;
  14. bool check(int i){
  15.     int &ret = dp[i];
  16.     if(~ret) return ret;
  17.     ret = 0;
  18. 	for(auto j : primes){
  19. 		if(i+j<=n&&i+j>=1&&idx[i+j]<idx[i]){
  20. 			ret |= !check(i+j);
  21. 		}
  22. 		if(i-j>n) cout<<5/0<<endl;
  23. 		if(i-j>=1&&i-j<=n&&idx[i-j]<idx[i]){
  24.             ret |= !check(i-j);
  25. 		}
  26. 	}
  27. 	return ret;
  28. }
  29. void solve(){
  30. 	cin>>n;
  31. 	if(dp[n]){
  32.         for(int i=1;i<n;i++) cout<<i<<' ';
  33.         cout<<n<<endl;
  34.         return;
  35. 	}
  36. 	int lst = -1;
  37. 	for(int i=1;i<=n;i++){
  38. 		if(dp[i]) lst = i;
  39.         idx[i] = i;
  40. 	}
  41. 	if(lst == -1){
  42.         cout<<-1<<endl;
  43.         return;
  44. 	}
  45. 	map<int,int> mp;
  46. 	vector<int> tmp;
  47. 	for(int i=1;i<=n;i++){
  48.         mp[i] = dp[i];
  49.         if(i>=lst)tmp.push_back(i);
  50. 	}
  51. 	vector<int> ans;
  52. 	do{
  53.         for(int i=1;i<=n;i++) dp[i] = -1;
  54.         int in = 0;
  55.         for(int i=lst;i<=n;i++){
  56.             if(tmp[i-lst] == n) in=i;
  57.             idx[i] = tmp[i-lst];
  58.         }
  59.         if(check(in)){
  60.             if(ans.size() == 0) ans = tmp;
  61.             else {
  62.                 for(int j=0;j<ans.size();j++){
  63.                     if(ans[j]>tmp[j]){
  64.                         ans = tmp;
  65.                         break;
  66.                     }
  67.                     else if(ans[j]<tmp[j]) break;
  68.                 }
  69.             }
  70.         }
  71. 	}while(next_permutation(tmp.begin(),tmp.end()));
  72. 	for(int i=1;i<lst;i++) cout<<i<<' ';
  73. 	int sz = ans.size();
  74. 	for(int i=0;i<sz-1;i++) cout<<ans[i]<<' ';
  75. 	cout<<ans.back()<<endl;
  76.     for(auto i : mp) {
  77.         dp[i.first] = i.second;
  78.     }
  79. }
  80. int main(){
  81. 	ios_base::sync_with_stdio(0);
  82. 	cin.tie(0);		 cout.tie(0);
  83. 	int t=1;
  84. 	cin>>t;
  85. 	memset(isPrime,1,sizeof(isPrime));
  86. 	isPrime[1] = 0;
  87. 	for(int i=2;i*i<N;i++){
  88. 		if(!isPrime[i]) continue;
  89. 		for(int j=i*i;j<N;j+=i){
  90. 			isPrime[j] = 0;
  91. 		}
  92. 		primes.push_back(i);
  93. 	}
  94. 	dp[1] = 0;
  95. 	dp[2] = 0;
  96. 	vector<int> tmp2;
  97. 	for(int i=3;i<N;i++){
  98. 		for(auto j : primes){
  99. 			if(j>=i) break;
  100. 			dp[i] |= !(dp[i-j]);
  101. 		}
  102. 	}
  103. 	while(t--){
  104. 		solve();
  105. 	}
  106. 	return 0;
  107. }
Success #stdin #stdout 0.02s 5460KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/spPT55
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
public

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!