QOJ.ac

QOJ

IDSubmission IDProblemHackerOwnerResultSubmit timeJudge time
#453#247695#7629. Make SYSU Great Again IIsjw712ucup-team087Failed.2023-11-15 12:08:492023-11-15 12:08:50

Details

Extra Test:

Accepted
time: 265ms
memory: 19724kb

input:

2000

output:

Yes
0 4190568 3730 4186476 5777 4178286 13968 4180325 9882 4182372 11929 4161894 30360 4163938 26268 4165985 18078 4174176 20106 4170100 22153 4129142 63112 4131186 59020 4133233 50830 4141424 52869 4137338 54916 4139385 34438 4157816 36482 4153724 38529 4145534 46720 4147498 42708 4149545 44758 406...

result:

ok 1

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#247695#7629. Make SYSU Great Again IIucup-team087#AC ✓266ms19604kbC++143.0kb2023-11-11 15:33:122023-11-11 15:33:12

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


constexpr int E = 13;
vector<int> seqs[E];

int getE(int n) {
  if (n % 2 == 0) {
    ++n;
  }
  for (int e = 1; e < E; ++e) {
    if (2 * (int)seqs[e].size() >= n) {
      return e;
    }
  }
  assert(false);
}

int a[2010][2010];

void solve(int n) {
  if (n % 2 == 0) {
    ++n;
  }
  const int e = getE(n);
  const int len = seqs[e].size();
  for (int x = 0; x < n; ++x) for (int y = 0; y < n; ++y) {
    const int hi = seqs[e][(x + y) % n % len];
    const int lo = seqs[e][(x - y + n) % n % len];
    a[x][y] = hi << e | lo;
  }
}

int main() {
  seqs[1] = {0, 1};
  for (int e = 2; e < E; ++e) {
    for (int i = 0; i < (int)seqs[e - 1].size(); ++i) {
      seqs[e].push_back(seqs[e - 1][i] | (i & 1) << (e - 1));
    }
    if (seqs[e].size() % 2 == 0) seqs[e].pop_back();
    for (int i = 0; i < (int)seqs[e - 1].size(); ++i) {
      seqs[e].push_back(seqs[e - 1][i] | ((i & 1) ^ 1) << (e - 1));
    }
// cerr<<e<<": "<<seqs[e].size()<<" "<<seqs[e]<<endl;
  }
  for (int e = 1; e < E; ++e) {
    const int len = seqs[e].size();
    for (int i = 0; i < len; ++i) {
      assert(0 <= seqs[e][i]); assert(seqs[e][i] < 1 << e);
      assert(!(seqs[e][i] & seqs[e][(i + 1) % len]));
    }
    assert(set<int>(seqs[e].begin(), seqs[e].end()).size() == seqs[e].size());
  }
  
#ifdef LOCAL
  for (int n = 1; n <= 2000; ++n) {
    const int e = getE(n);
if(n<=20)cerr<<n<<": "<<e<<endl;
    assert(1 << (2 * e) <= 4 * n * n);
  }
#endif
  
  int N;
  for (; ~scanf("%d", &N); ) {
    solve(N);
    puts("Yes");
    for (int x = 0; x < N; ++x) {
      for (int y = 0; y < N; ++y) {
        if (y) printf(" ");
        printf("%d", a[x][y]);
      }
      puts("");
    }
  }
  return 0;
}