fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. typedef long long ll;
  5. typedef pair<int,int> pii;
  6. const int arr = 150;
  7. const int tarr = 14400;
  8. const ll mod = 1e9+7;
  9. const ll maxv = 1e18+1;
  10. #define fi first
  11. #define se second
  12. #define vi vector<int>
  13. #define pb push_back
  14. #define mp make_pair
  15. #define all(v) v.begin(), v.end()
  16. #define no "NO\n"
  17. #define yes "YES\n"
  18. #define ld long double
  19. #define mat vector<vector<ll>>
  20. #define int long long
  21. int n, a[arr][arr];
  22. int dr[8] = {-2, -2, -1, 1, 2, 2, 1, -1};
  23. int dc[8] = {-1, 1, 2, 2, 1, -1, -2, -2};
  24. bool found;
  25. int s;
  26. vector<pii> path;
  27.  
  28. bool ck(int r, int c){
  29.     return (r > 0 && c > 0 && r <= n && c <= n);
  30. }
  31.  
  32. int calc(int x, int y){
  33.     int cnt = 0;
  34.     for(int i = 0; i < 8; ++i){
  35.         int nx_x = x + dr[i], nx_y = y + dc[i];
  36.         if(ck(nx_x, nx_y) && !a[nx_x][nx_y]) ++cnt;
  37.     }
  38.     return cnt;
  39. }
  40.  
  41. void dfs(int r, int c, int id){
  42.     a[r][c] = id;
  43.     path.pb({r, c});
  44.     s += (r+c)*id;
  45.     if(id == n*n){
  46.         found = true;
  47.         return;
  48.     }
  49.     int bestx = 0, besty = 0, bestcnt = -1;
  50.     for(int i = 0; i < 8; ++i){
  51.         int x = r + dr[i], y = c + dc[i];
  52.         if(!ck(x, y) || a[x][y]) continue;
  53.         int cnt = calc(x, y);
  54.         if(bestcnt == -1 || cnt < bestcnt || cnt == bestcnt && x+y < bestx+besty){
  55.             bestcnt = cnt;
  56.             bestx = x, besty = y;
  57.         }
  58.     }
  59.     dfs(bestx, besty, id+1);
  60.     if(found) return;
  61.     a[r][c] = 0;
  62. }
  63. /** 15234589164 **/
  64. void solve(){
  65.     int best = 0, bestx = 0, besty = 0, bestid = 0;
  66.     for(int x = n/2; x <= n; ++x){
  67.         for(int y = 1; y <= n/2; ++y){
  68.             memset(a, 0, sizeof a);
  69.             found = false;
  70.             s = 0;
  71. 			path.clear();
  72.             dfs(x, y, 1);
  73. 			int sum = 0;
  74.             for(int i = path.size()-1; i >= 0; --i){
  75. 			    sum += (n*n - i)*(path[i].fi + path[i].se);
  76. 			}
  77. 			if(sum > best) best = sum, bestx = x, besty = y, bestid = 1;
  78. 			if(s > best) best = s, bestx = x, besty = y, bestid = 0;
  79.         }
  80.     }
  81.     cout << bestx << " " << besty << '\n';
  82.     cout << best << " " << bestid << '\n';
  83. }
  84.  
  85. signed main(){
  86.     cin.tie(nullptr)->sync_with_stdio(false);
  87.     cin >> n;
  88.     solve();
  89.     return 0;
  90. }
  91.  
Success #stdin #stdout 9.46s 5668KB
comments (?)
stdin
copy 
120
stdout
copy 
64 59
15209647796 0
https://ideone.com/2tSiHV
language:
C++14 (gcc 8.3)
created:
3 days 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!