fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define REP(a, b) for(int a = 0; a < b; a++)
  3. #define FOR(i, a, b) for(int i = a; i <= b; i++)
  4. #define mp make_pair
  5. #define f first
  6. #define s second
  7. #define pb push_back
  8. using namespace std;
  9.  
  10. typedef long long ll;
  11. typedef pair<int, int> ii;
  12. typedef pair<ll, ll> LL;
  13. typedef vector<int> vi;
  14.  
  15. const ll INF = 1e9;
  16. const ll MOD = 1e9 + 7;
  17. const int MAXN = 1e5 + 100;
  18.  
  19. int n;
  20. vector<ii> prime[MAXN];
  21. int g[MAXN];
  22. int x[MAXN];
  23. int mv[MAXN];
  24.  
  25. void pre() {
  26. 	FOR(i, 1, 100000) {
  27. 		int sek = i;
  28. 		int bat = sqrt(i);
  29. 		FOR(j, 1, bat) {
  30. 			if (i % j == 0) {
  31. 				int a = j;
  32. 				int b = i / j;
  33. 				if (a % 2 == 1 || b % 2 == 1) {
  34. 					prime[i].pb(mp(a, b));
  35. 				}
  36. 			}
  37. 		}
  38. 	}
  39. }
  40.  
  41. int main() {
  42. 	//freopen("input.txt", "r", stdin);
  43. 	//freopen("output.txt", "w", stdout);
  44. 	ios::sync_with_stdio(0); cin.tie(0);
  45. 	REP(i, MAXN) mv[i] = INF;
  46. 	cin >> n;
  47. 	pre();
  48. 	g[0] = g[1] = g[2] = 0;
  49. 	x[0] = g[0]; x[1] = x[0] ^ g[1]; x[2] = x[1] ^ g[2];
  50. 	FOR(i, 3, n) {
  51. 		unordered_set<int> st;
  52. 		REP(j, prime[i].size()) {
  53. 			int a = prime[i][j].f, b = prime[i][j].s;
  54. 			if (i == n) cout << a << ' ' << b << "eA\n";
  55. 			if (a % 2 == 1) {
  56. 				int x1 = a, x2 = b * 2;
  57. 				if (x1 < x2) swap(x1, x2);
  58. 				int besar = (x1 + x2 - 1) / 2, kecil = (x1 - x2 - 1) / 2;
  59. 				if (i == n) cout << besar << ' ' << kecil << ' ' << (x[besar] ^ x[kecil]) << " 1MANTA\n";
  60. 				if (besar - kecil >= 2) {
  61. 					st.insert(x[besar] ^ x[kecil]);
  62. 					if (i == n)cout << (x[besar] ^ x[kecil]) << " COBA\n";
  63. 					if ((x[besar] ^ x[kecil]) == 0 && besar - kecil < mv[i]) {
  64. 						if (i == n) cout << (x[besar] ^ x[kecil]) << " COBAe\n";
  65. 						mv[i] = besar - kecil;
  66. 					}
  67. 				}
  68. 			}
  69. 			if (a != b){
  70. 				if (b % 2 == 1) {
  71. 					int x1 = b, x2 = a * 2;
  72. 					if (x1 < x2) swap(x1, x2);
  73. 					int besar = (x1 + x2 - 1) / 2, kecil = (x1 - x2 - 1) / 2;
  74. 					if (i == n) cout << besar << ' ' << kecil << ' ' << (x[besar] ^ x[kecil]) << " MANTA\n";
  75. 					if (besar - kecil >= 2) {
  76. 						st.insert(x[besar] ^ x[kecil]);
  77. 						if (i == n) cout << (x[besar] ^ x[kecil]) << " COBA\n";
  78. 						if ((x[besar] ^ x[kecil]) == 0 && besar - kecil < mv[i]) {
  79. 							if (i == n) cout << (x[besar] ^ x[kecil]) << " COBAe\n";
  80. 							mv[i] = besar - kecil;
  81. 						}	
  82. 					}
  83. 				}	
  84. 			}
  85. 		}
  86. 		int now = 0;
  87. 		while(st.find(now) != st.end()) now++;
  88. 		g[i] = now;
  89. 		x[i] = x[i - 1] ^ g[i];
  90. 	}
  91. 	if (g[n] == 0) cout << -1 << '\n';
  92. 	else cout << mv[n] << '\n';
  93. }
Success #stdin #stdout 0.06s 24432KB
comments (?)
stdin
copy 
250
stdout
copy 
1 250eA
250 249 6 1MANTA
2 125eA
64 60 1 MANTA
1 COBA
5 50eA
52 47 0 1MANTA
0 COBA
0 COBAe
10 25eA
22 2 0 MANTA
0 COBA
5
https://ideone.com/OzaSka
language:
C++14 (gcc 8.3)
created:
5 years 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!