QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#281364#7178. Bishopsikaurov#WA 0ms3888kbC++203.1kb2023-12-10 03:22:272023-12-10 03:22:28

Judging History

你现在查看的是最新测评结果

  • [2023-12-10 03:22:28]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3888kb
  • [2023-12-10 03:22:27]
  • 提交

answer

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define all(arr) (arr).begin(), (arr).end()
#define ll long long
#define ld long double
#define pb push_back
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define endl '\n'

vector<pair<int, int>> stupid_vertical(int n){
  vector<pair<int, int>> ret;
  for (int i = 1; i <= n; i++) ret.pb({1, i});
  return ret;
}

vector<pair<int, int>> stupid_horizontal(int n){
  vector<pair<int, int>> ret;
  for (int i = 1; i <= n; i++) ret.pb({i, 1});
  return ret;
}

vector<pair<int, int>> smart_square(int n){
  vector<pair<int, int>> ret;
  for (int i = 1; i <= n; i++) ret.pb({i, 1});
  for (int i = 2; i < n; i++) ret.pb({i, n});
  return ret;
}

vector<pair<int, int>> place(int n, int m){

  if (n % 2 == 1 && m == 2 * n){
    vector<pair<int, int>> ret;
    for (int i = 1; i <= n; i++){
      ret.pb({i, 1});
      ret.pb({i, m});
      if (i % 2 == 0) ret.pb({i, n}), ret.pb({i, n + 1});
    }
    return ret;
  }

  if (m % 2 == 1 && n == 2 * m){
    vector<pair<int, int>> ret;
    for (int i = 1; i <= m; i++){
      ret.pb({1, i});
      ret.pb({m, i});
      if (i % 2 == 0) ret.pb({m, i}), ret.pb({m + 1, i});
    }
    return ret;
  }

  if (n == m){
    return smart_square(n);
  }
  else{
    if (n > m){
      vector<pair<int, int>> ret;
      int i = 0;
      for (; i + m + (m % 2 == 1 && n % m == 0? m : 0) < n; i += m){
        auto cur = stupid_vertical(m);
        for (auto [x, y] : cur){
          ret.pb({x + i, y});
        }
      }
      vector<pair<int, int>> rem;
      if (m % 2 == 1 && n % m == 0){
        rem = place(2 * m, m);
      }
      else if (n % m == 0) rem = smart_square(m);
      else rem = place(n % m, m);
      for (auto [x, y] : rem) ret.pb({x + i, y});
      return ret;
    }
    else{
      vector<pair<int, int>> ret;
      int i = 0;
      for (; i + n + (n % 2 == 1 && m % n == 0? n : 0) < m; i += n){
        auto cur = stupid_horizontal(n);
        for (auto [x, y] : cur){
          ret.pb({x, y + i});
        }
      }
      vector<pair<int, int>> rem;
      if (n % 2 == 1 && m % n == 0){
        rem = place(n, 2 * n);
      }
      else if (m % n == 0) rem = smart_square(n);
      else rem = place(n, m % n);
      for (auto [x, y] : rem) ret.pb({x, y + i});
      return ret;
    }
  }
}

void check(int n, int m, vector<pair<int, int>> ans){
  int need = n + m - 1 - (__gcd(n, m) > 1);
  // assert(sz(ans) == need);
  for (int i = 0; i < sz(ans); i++){
    for (int j = 0; j < i; j++){
      int x1 = ans[i].fi, y1 = ans[i].se;
      int x2 = ans[j].fi, y2 = ans[j].se;

      assert(x1 + y1 != x2 + y2);
      assert(x1 - y1 != x2 - y2);
    }
  }
}

signed main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  // cout.precision(20);
  // for (int n = 1; n < 200; n++){
  //   for (int m = 1; m < 200; m++){
  //     check(n, m, place(n, m));
  //   }
  // }
  int n, m;
  cin >> n >> m;
  auto ans = place(n, m);
  cout << sz(ans) << endl;
  for (auto [x, y] : ans) cout << x << " " << y << endl;
  // check(n, m, ans);
}

详细

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3888kb

input:

2 5

output:

6
1 1
2 1
1 3
2 3
1 5
1 5

result:

wrong answer Sum diagonals are not distinct