• API
• FAQ
• Tools
• Archive
SHARE
TWEET # Untitled a guest Oct 18th, 2019 82 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top