#1189406 (C++23) No.3734 No Flat Notes

• 問題: No.3734 No Flat Notes
• ユーザー: HoyHoyCharhang
• 提出日時: 2026-09-19 17:39:17
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 14 ms / 2,000 ms
• コード長: 7,038 bytes
• コンパイル時間: 2,361 ms
• コンパイル使用メモリ: 355,300 KB
• 実行使用メモリ: 6,528 KB
• 最終ジャッジ日時: 2026-09-19 17:39:31
• 合計ジャッジ時間: 6,799 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_0

サブタスク	配点	結果
部分点	20 %	AC * 28
満点	80 %	AC * 60
合計	3.5 * 100% = 350 点

ソースコード

#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,s,n) for (int i = (s); i < (n); ++i)
#define rrep(i,g,n) for (int i = (n)-1; i >= (g); --i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define len(x) (int)(x).size()
#define dup(x,y) (((x)+(y)-1)/(y))
#define pb push_back
#define eb emplace_back
#define Field(T) vector<vector<T>>
using namespace std;
using ll = long long;
using ull = unsigned long long;
template<typename T> using pq = priority_queue<T,vector<T>,greater<T>>;
using P = pair<int,int>;
template<class T>bool chmax(T&a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T&a,T b){if(b<a){a=b;return 1;}return 0;}

void naive(int h, int w, int m) {
  vector<int> p(h*w);
  iota(all(p), 0);
  do {
    vector<vector<int>> a(h, vector<int>(w));
    rep(i,0,h) rep(j,0,w) a[i][j] = p[i*w+j];
    int c1 = 0, c2 = 0;
    rep(i,0,h) rep(j,0,w) {
      int x = 0, y = 0;
      if (i+1 < h && a[i][j] < a[i+1][j]) ++x;
      if (j+1 < w && a[i][j] < a[i][j+1]) ++x;
      if (i > 0 && a[i][j] < a[i-1][j]) ++x;
      if (j > 0 && a[i][j] < a[i][j-1]) ++x;
      if (i+1 < h && a[i][j] > a[i+1][j]) ++y;
      if (j+1 < w && a[i][j] > a[i][j+1]) ++y;
      if (i > 0 && a[i][j] > a[i-1][j]) ++y;
      if (j > 0 && a[i][j] > a[i][j-1]) ++y;
      if (x > 0 && y == 0) ++c1;
      if (y > 0 && x == 0) ++c2;
    }
    if (c1 == m && c2 == m) {
      rep(i,0,h) {
        rep(j,0,w) {
          cout << a[i][j]+1 << " ";
        }
        cout << endl;
      }
      return;
    }
  } while(next_permutation(all(p)));
}

int main() {
  int h, w, m;
  cin >> h >> w >> m;
  if ((h*w)%2 == 0) {
    if (m == 0) {
      cout << -1 << endl;
      return 0;
    }
    int is_flip = 0;
    if (h%2 == 1 || w == 2) {
      swap(h, w);
      is_flip = 1;
    }
    vector<vector<int>> a(h, vector<int>(w));
    if (m >= h/2) {
      int val = 0;
      rep(i,0,w) {
        rep(j,0,h/2) {
          if (i%2 == 0) a[2*j][i] = ++val;
          else a[h-2*j-1][i] = ++val;
        }
      }
      val = h*w;
      rep(i,0,w) {
        rep(j,0,h/2) {
          if (i%2 == 0) a[2*j+1][i] = val--;
          else a[h-2*j-2][i] = val--;
        }
      }
      // rep(i,0,h) {
      //   rep(j,0,w) cout << a[i][j] << " ";
      //   cout << endl;
      // }
      int c = (h*w-2*m)/2;
      int k = ((h*w-2*m)/2)/(h/2);
      // cout << k << endl;
      if ((w-k-1)%2 == 1) {
        rep(i,0,h/2) {
          if (i < c%(h/2)) {
            swap(a[2*i][w-k-1], a[2*i+1][w-k-1]);
            rep(j,0,k) {
              if (j%2 == 1) swap(a[2*i][w-k+j], a[2*i+1][w-k+j]); 
            }
          } else {
            rep(j,0,k) {
              if (j%2 == 0) swap(a[2*i][w-k+j], a[2*i+1][w-k+j]); 
            }
          }
        }
      } else {
        rrep(i,0,h/2) {
          if ((h/2-i-1) < c%(h/2)) {
            swap(a[2*i][w-k-1], a[2*i+1][w-k-1]);
            rep(j,0,k) {
              if (j%2 == 1) swap(a[2*i][w-k+j], a[2*i+1][w-k+j]); 
            }
          } else {
            rep(j,0,k) {
              if (j%2 == 0) swap(a[2*i][w-k+j], a[2*i+1][w-k+j]); 
            }
          }
        }
      }
    } else {
      int val = 0;
      rep(i,0,w) {
        rep(j,0,h) {
          if (i%2 == 0) a[j][i] = ++val;
          else a[h-j-1][i] = ++val;
        }
      }
      rep(i,0,m) {
        if (i%2 == 0) {
          a[m-i-1][0] = i+1;
          a[(w%2 == 0 ? m-i-1 : h-(m-i-1)-1)][w-1] = h*w-i;
        } else {
          a[m-i-1][0] = h*w-i;
          a[(w%2 == 0 ? m-i-1 : h-(m-i-1)-1)][w-1] = i+1;
        }
      }
    }
    if (is_flip) {
      vector<vector<int>> na(w, vector<int>(h));
      rep(i,0,h) rep(j,0,w) na[j][i] = a[i][j];
      swap(a, na), swap(h, w);
    }
    rep(i,0,h) {
      rep(j,0,w) cout << a[i][j] << " ";
      cout << endl;
    }
    return 0;
  }
  // naive(h, w, m);
  int is_flip = 0;
  if (h < w) swap(h, w), is_flip = 1;
  vector<vector<int>> a(h, vector<int>(w));
  if (w == 1) {
    if (h == 1) {
      a[0][0] = 1;
    } else {
      if (m == 0) {
        cout << -1 << endl;
        return 0;
      }
      rep(i,0,h) a[i][0] = i+1;
      rep(i,0,m) {
        if (i%2 == 0) {
          a[m-i-1][0] = i+1;
          a[h-(m-i-1)-1][0] = h*w-i;
        } else {
          a[m-i-1][0] = h*w-i;
          a[h-(m-i-1)-1][0] = i+1;
        }
      }
    }
  } else {
    if (m == 0) {
      cout << -1 << endl;
      return 0;
    }
    if (m <= h) {
      int val = 0;
      rep(i,0,w) {
        rep(j,0,h) {
          if (i%2 == 0) a[j][i] = ++val;
          else a[h-j-1][i] = ++val;
        }
      }
      rep(i,0,m) {
        if (i%2 == 0) {
          a[m-i-1][0] = i+1;
          a[(w%2 == 0 ? m-i-1 : h-(m-i-1)-1)][w-1] = h*w-i;
        } else {
          a[m-i-1][0] = h*w-i;
          a[(w%2 == 0 ? m-i-1 : h-(m-i-1)-1)][w-1] = i+1;
        }
      }
    } else if (m < ((h-1)/2)*w) {
      int flag = 0;
      if (h%4 == 3 && m == ((h-1)/2)*w-1) {
        --m;
        flag = 1;
      }
      int val = 0;
      rep(i,0,h) {
        rep(j,0,w) {
          if (i%2 == 0) a[i][j] = ++val;
          else a[i][w-j-1] = ++val;
        }
      }
      int cnt = m/2;
      // cout << cnt << endl;
      int i0 = -1, j0 = -1;
      rep(i,0,h) {
        if (i%2 == 0) {
          rep(j,0,w) {
            if (j%2 == 1) {
              if (cnt) swap(a[i][j], a[h-i-1][w-j-1]), --cnt;
              if (cnt == 0 && i0 == -1) i0 = i, j0 = j;
            }
          }
        } else {
          rrep(j,0,w) {
            if (j%2 == 0) {
              if (cnt) swap(a[i][j], a[h-i-1][w-j-1]), --cnt;
              if (cnt == 0 && i0 == -1) i0 = i, j0 = j;
            }
          }
        }
      }
      // cout << i0 << " " << j0 << endl;
      if ((m < ((h-1)/2)*w && m%2 == 0) || flag) {
        int i1 = 0, j1 = 0, j2 = 0;
        if (flag) {
          i1 = (h-3)/2, j1 = w-1, j2 = w-2;
        } else if (i0%2 == 0) {
          if (j0 == w-2) {
            i1 = i0+1, j1 = w-2, j2 = w-1;
          } else {
            i1 = i0, j1 = j0+1, j2 = j0+2;
          }
        } else {
          if (j0 == 0) {
            i1 = i0+1, j1 = 0, j2 = 1;
          } else {
            i1 = i0, j1 = j0-1, j2 = j0-2;
          }
        }
        // cout << i1 << " " << j1 << " " << j2 << endl;
        swap(a[i1][j1], a[i1][j2]);
        swap(a[h-i1-1][w-j1-1], a[h-i1-1][w-j2-1]);
      }
    } else {
      int v1 = 0, v2 = h*w;
      rep(i,0,h) rep(j,0,w) {
        if ((i+j)%2 == 0) a[i][j] = ++v1;
        else a[i][j] = v2--;
      }
      sort(all(a[h-1]));
      int d = m-((h-1)/2)*w;
      if (2*m == h*w-1) {
        cout << -1 << endl;
        return 0;
      }
      swap(a[h-1][0], a[h-1][1]);
      rep(i,0,d) {
        swap(a[h-1][w-(2*i)-1], a[h-1][w-(2*i+1)-1]);
      }
    }
  }
  if (is_flip) {
    vector<vector<int>> na(w, vector<int>(h));
    rep(i,0,h) rep(j,0,w) na[j][i] = a[i][j];
    swap(a, na), swap(h, w);
  }
  rep(i,0,h) {
    rep(j,0,w) cout << a[i][j] << " ";
    cout << endl;
  }
  return 0;
}