提出 #74068201

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main(){
  ll N,x = 0,y = 0,score = 0,score2 = 0,score3 = 0,score4 = 0,score5 = 0,M;
  cin >> N;
  vector<vector<ll>> A(N,vector<ll>(N));
  for(ll i = 0;i < N;i++){
    for(ll j = 0;j < N;j++){
      cin >> A[i][j];
    }
  }
  queue<pair<ll,ll>> B;
  B.push({0,0});
  function<void(char)> move = [&](char c){
    if(c == 'U'){
      x--;
    }
    if(c == 'D'){
      x++;
    }
    if(c == 'L'){
      y--;
    }
    if(c == 'R'){
      y++;
    }
    B.push({x,y});
  };
  for(ll i = 0;i < N / 2 - 1;i++){
    move('D');
    move('R');
    move('D');
    move('L');
  }
  move('D');
  move('R');
  move('R');
  for(ll i = 0;i < N / 4 - 1;i++){
    for(ll j = 0;j < N / 2 - 1;j++){
      move('R');
      move('U');
      move('L');
      move('U');
    }
    move('R');
    move('R');
    for(ll j = 0;j < N / 2 - 1;j++){
      move('R');
      move('D');
      move('L');
      move('D');
    }
    move('R');
    move('R');
  }
  for(ll i = 0;i < N / 2 - 1;i++){
    move('R');
    move('U');
    move('L');
    move('U');
  }
  move('R');
  move('U');
  for(ll i = 0;i < N - 2;i++){
    move('L');
  }
  while(1){
    if(A[B.front().first][B.front().second] == N * N){
      B.push(B.front());
      B.pop();
      break;
    }
    B.push(B.front());
    B.pop();
  }
  vector<pair<ll,ll>> ans(N * N);
  for(ll i = 0;i < N * N;i++){
    ans[i] = B.front();
    B.pop();
  }
  set<pair<ll,ll>> C;
  for(ll i = 0;i < N;i+=2){
    C.insert({i,0});
    C.insert({N - 1 - i,N - 1});
  }
  for(ll j = 3;j < N - 1;j+=4){
    for(ll i = N - 1;i >= 3;i-=2){
      C.insert({i,j});
      C.insert({i - 1,j + 1});
    }
  }
  for(ll i = 1;i < N * N - 1;i++){
    if(C.count(ans[i])){
      if(A[ans[i].first][ans[i].second] > A[ans[i + 1].first][ans[i + 1].second]){
        swap(ans[i],ans[i + 1]);
        i++;
      }
    }
  }
  for(ll i = 0;i < N * N;i++){
    score+=(i + 1) * A[ans[i].first][ans[i].second];
  }
  for(ll t = 0;t < N / 2;t++){
    for(ll j = 0;j < N;j++){
      score2+=(t * N * 2 + j + 1) * A[t * 2][j];
      score3+=(t * N * 2 + j + 1) * A[N - 1 - t * 2][N - 1 - j];
      score4+=(t * N * 2 + j + 1) * A[j][t * 2];
      score5+=(t * N * 2 + j + 1) * A[N - 1 - j][N - 1 - t * 2];
    }
    for(ll j = N - 1;j >= 0;j--){
      score2+=(t * N * 2 + N + N - j) * A[t * 2 + 1][j];
      score3+=(t * N * 2 + N + N - j) * A[N - 1 - (t * 2 + 1)][N - 1 - j];
      score4+=(t * N * 2 + N + N - j) * A[j][t * 2 + 1];
      score5+=(t * N * 2 + N + N - j) * A[N - 1 - j][N - 1 - (t * 2 + 1)];
    }
  }
  M = max({score,score2,score3,score4,score5});
  if(M == score){
    for(ll i = 0;i < N * N;i++){
      cout << ans[i].first << " " << ans[i].second << endl;
    }
    return 0;
  }
  if(M == score2){
    for(ll t = 0;t < N / 2;t++){
      for(ll j = 0;j < N;j++){
        cout << t * 2 << " " << j << endl;
      }
      for(ll j = N - 1;j >= 0;j--){
        cout << t * 2 + 1 << " " << j << endl;
      }
    }
    return 0;
  }
  if(M == score3){
    for(ll t = 0;t < N / 2;t++){
      for(ll j = 0;j < N;j++){
        cout << N - 1 - t * 2 << " " << N - 1 - j << endl;
      }
      for(ll j = N - 1;j >= 0;j--){
        cout << N - 1 - (t * 2 + 1) << " " << N - 1 - j << endl;
      }
    }
    return 0;
  }
  if(M == score4){
    for(ll t = 0;t < N / 2;t++){
      for(ll j = 0;j < N;j++){
        cout << j << " " << t * 2 << endl;
      }
      for(ll j = N - 1;j >= 0;j--){
        cout << j << " " << t * 2 + 1 << endl;
      }
    }
    return 0;
  }
  if(M == score5){
    for(ll t = 0;t < N / 2;t++){
      for(ll j = 0;j < N;j++){
        cout << N - 1 - j << " " << N - 1 - t * 2 << endl;
      }
      for(ll j = N - 1;j >= 0;j--){
        cout << N - 1 - j << " " << N - 1 - (t * 2 + 1) << endl;
      }
    }
    return 0;
  }
}

提出情報

ジャッジ結果