# Untitled

a guest
Oct 18th, 2019
85
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <iostream>
2. #include <vector>
3. #include <algorithm>
4. #include <cmath>
5.
6. #define pb push_back
7. #define mp make_pair
8. #define int long long
9. #define f first
10.
11. using namespace std;
12.
13. int n, best = 1000;
14. vector<int> ans;
15. bool fin;
16.
17. int get_err(vector<int>& v) {
18. int err = 0;
19. for (int i = 0; i < n; ++i)
20. for (int j = i+1; j < n; ++j) {
21. if (abs(i-j) == abs(v[i]-v[j])) {
22. ++err;
23. }
24. }
25. return err;
26. }
27.
28. void rec(vector<int> v, double t) {
29. if (t < 0.00001 || fin) return;
30.
31. int err = get_err(v);
32. if (!err) {
33. fin = true;
34. ans = v;
35. return;
36. }
37.
38. int i = rand()%n;
39. int j = rand()%n;
40. if (i == j) j = (i+1)%n;
41.
42. swap(v[i], v[j]);
43.
44. double rand_num = (rand()%1000)/1000;
45. double conf = std::exp(double(best-err)/t);
46. cout << conf << '\n';
47. best = min(best, err);
48. if (rand_num < conf) rec(v, t*0.98);
49. }
50.
51. signed main() {
52. cin >> n;
53.
54. while (!fin) {
55. vector<int> v(n);
56. for (int i = 0; i < n; ++i) v[i] = i;
57. random_shuffle(v.begin(), v.end());
58. rec(v, 400);
59. }
60.
61. for (int i = 0; i < n; ++i) cout << ans[i]+1 << ' ';
62.
63. return 0;
64. }
RAW Paste Data