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. OK, I Understand
 
Top