QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#229758#7637. Exactly Three Neighborsucup-team087#AC ✓1ms3776kbC++144.1kb2023-10-28 16:49:492023-10-28 16:49:50

Judging History

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

  • [2023-10-28 16:49:50]
  • 评测
  • 测评结果:AC
  • 用时:1ms
  • 内存:3776kb
  • [2023-10-28 16:49:49]
  • 提交

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 DX[4] = {+1, 0, -1, 0};
constexpr int DY[4] = {0, +1, 0, -1};

vector<string> solve(int P, int Q) {
  // P/Q <= 2/3
  if (3 * P <= 2 * Q) {
    string a(2 * Q, '.');
    for (int i = 0; i < P; ++i) {
      a[3 * i] = a[3 * i + 1] = '#';
    }
    return {a};
  } else if (P == 3 && Q == 4) {
    vector<string> a(4, string(4, '#'));
    a[0][0] = a[0][1] = a[2][2] = a[2][3] = '.';
    return a;
  } else if (P == 4 && Q == 5) {
    vector<string> a(5, string(5, '#'));
    for (int x = 0; x < 5; ++x) {
      a[x][(2 * x) % 5] = '.';
    }
    return a;
  } else if (P == 5 && Q == 7) {
    vector<string> a(14, string(4, '#'));
    a[0][0] = a[0][1] = a[1][0] = a[1][1] = a[3][2] = a[3][3] = a[5][0] = a[5][1] = '.';
    for (int x = 0; x < 7; ++x) for (int y = 0; y < 4; ++y) {
      a[x + 7][(y + 2) % 4] = a[x][y];
    }
    return a;
  } else if (P == 7 && Q == 9) {
    vector<string> a(18, string(6, '#'));
    for (int i = 0; i < 6; ++i) {
      a[3 * i + 0][(i + 0) % 6] = '.';
      a[3 * i + 0][(i + 1) % 6] = '.';
      a[3 * i + 1][(i + 3) % 6] = '.';
      a[3 * i + 2][(i + 5) % 6] = '.';
    }
    return a;
  } else if (P == 7 && Q == 10) {
    vector<string> a(5, string(4, '#'));
    a[0][0] = a[0][1] = a[1][0] = a[1][1] = a[3][2] = a[3][3] = '.';
    return a;
  } else {
    return {};
  }
}

void judge(int P, int Q, const vector<string> &a) {
  const int m = a.size(), n = a[0].size();
  for (int x = 0; x < m; ++x) {
    assert((int)a[x].size() == n);
    for (int y = 0; y < n; ++y) {
      assert(a[x][y] == '#' || a[x][y] == '.');
    }
  }
  int cnt = 0;
  for (int x = 0; x < m; ++x) for (int y = 0; y < n; ++y) if (a[x][y] == '#') {
    ++cnt;
    int deg = 0;
    for (int dir = 0; dir < 4; ++dir) {
      const int xx = (x + DX[dir] + m) % m;
      const int yy = (y + DY[dir] + n) % n;
      if (a[xx][yy] == '#') {
        ++deg;
      }
    }
    assert(deg == 3);
  }
  // P/Q = cnt/mn
  assert(P * m * n == Q * cnt);
}

int main() {
#ifdef LOCAL
  for (int Q = 0; Q <= 10; ++Q) for (int P = 0; P <= Q; ++P) if (__gcd(P, Q) == 1) {
    cerr << COLOR("33") << P << "/" << Q << COLOR() << endl;
    const auto ans = solve(P, Q);
    if (!ans.empty()) {
      for (const auto &row : ans) {
        cerr << row << endl;
      }
      judge(P, Q, ans);
    } else {
      cerr << "no solution" << endl;
      // P/Q <= 4/5
      if (5 * P <= 4 * Q) {
        cerr << COLOR("31") << "TODO" << COLOR() << endl;
      }
    }
  }
#endif
  
  int P, Q;
  for (; ~scanf("%d%d", &P, &Q); ) {
    const auto ans = solve(P, Q);
    if (!ans.empty()) {
      printf("%d %d\n", (int)ans.size(), (int)ans[0].size());
      for (const auto &row : ans) {
        puts(row.c_str());
      }
    } else {
      puts("-1 -1");
    }
  }
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3724kb

input:

2 3

output:

1 6
##.##.

result:

ok good solution

Test #2:

score: 0
Accepted
time: 1ms
memory: 3512kb

input:

1 1

output:

-1 -1

result:

ok no solution

Test #3:

score: 0
Accepted
time: 1ms
memory: 3772kb

input:

3 4

output:

4 4
..##
####
##..
####

result:

ok good solution

Test #4:

score: 0
Accepted
time: 0ms
memory: 3664kb

input:

3 5

output:

1 10
##.##.##..

result:

ok good solution

Test #5:

score: 0
Accepted
time: 1ms
memory: 3636kb

input:

4 5

output:

5 5
.####
##.##
####.
#.###
###.#

result:

ok good solution

Test #6:

score: 0
Accepted
time: 0ms
memory: 3664kb

input:

7 10

output:

5 4
..##
..##
####
##..
####

result:

ok good solution

Test #7:

score: 0
Accepted
time: 0ms
memory: 3776kb

input:

5 7

output:

14 4
..##
..##
####
##..
####
..##
####
##..
##..
####
..##
####
##..
####

result:

ok good solution

Test #8:

score: 0
Accepted
time: 0ms
memory: 3672kb

input:

7 9

output:

18 6
..####
###.##
#####.
#..###
####.#
.#####
##..##
#####.
#.####
###..#
.#####
##.###
####..
#.####
###.##
.####.
##.###
####.#

result:

ok good solution

Test #9:

score: 0
Accepted
time: 0ms
memory: 3660kb

input:

0 1

output:

1 2
..

result:

ok good solution

Test #10:

score: 0
Accepted
time: 0ms
memory: 3696kb

input:

1 2

output:

1 4
##..

result:

ok good solution

Test #11:

score: 0
Accepted
time: 0ms
memory: 3652kb

input:

1 3

output:

1 6
##....

result:

ok good solution

Test #12:

score: 0
Accepted
time: 0ms
memory: 3652kb

input:

1 4

output:

1 8
##......

result:

ok good solution

Test #13:

score: 0
Accepted
time: 0ms
memory: 3624kb

input:

1 5

output:

1 10
##........

result:

ok good solution

Test #14:

score: 0
Accepted
time: 1ms
memory: 3660kb

input:

1 6

output:

1 12
##..........

result:

ok good solution

Test #15:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

1 7

output:

1 14
##............

result:

ok good solution

Test #16:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

1 8

output:

1 16
##..............

result:

ok good solution

Test #17:

score: 0
Accepted
time: 0ms
memory: 3668kb

input:

1 9

output:

1 18
##................

result:

ok good solution

Test #18:

score: 0
Accepted
time: 0ms
memory: 3760kb

input:

1 10

output:

1 20
##..................

result:

ok good solution

Test #19:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

2 5

output:

1 10
##.##.....

result:

ok good solution

Test #20:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

2 7

output:

1 14
##.##.........

result:

ok good solution

Test #21:

score: 0
Accepted
time: 0ms
memory: 3700kb

input:

2 9

output:

1 18
##.##.............

result:

ok good solution

Test #22:

score: 0
Accepted
time: 0ms
memory: 3764kb

input:

3 7

output:

1 14
##.##.##......

result:

ok good solution

Test #23:

score: 0
Accepted
time: 0ms
memory: 3732kb

input:

3 8

output:

1 16
##.##.##........

result:

ok good solution

Test #24:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

3 10

output:

1 20
##.##.##............

result:

ok good solution

Test #25:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

4 7

output:

1 14
##.##.##.##...

result:

ok good solution

Test #26:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

4 9

output:

1 18
##.##.##.##.......

result:

ok good solution

Test #27:

score: 0
Accepted
time: 0ms
memory: 3608kb

input:

5 6

output:

-1 -1

result:

ok no solution

Test #28:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

5 8

output:

1 16
##.##.##.##.##..

result:

ok good solution

Test #29:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

5 9

output:

1 18
##.##.##.##.##....

result:

ok good solution

Test #30:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

6 7

output:

-1 -1

result:

ok no solution

Test #31:

score: 0
Accepted
time: 0ms
memory: 3396kb

input:

7 8

output:

-1 -1

result:

ok no solution

Test #32:

score: 0
Accepted
time: 0ms
memory: 3452kb

input:

8 9

output:

-1 -1

result:

ok no solution

Test #33:

score: 0
Accepted
time: 1ms
memory: 3436kb

input:

9 10

output:

-1 -1

result:

ok no solution

Extra Test:

score: 0
Extra Test Passed