Submission #3177420


Source Code Expand

Copy
/* ---------- STL Libraries ---------- */

// IO library
#include <cstdio>
#include <fstream>
#include <iomanip>
#include <ios>
#include <iostream>

// algorithm library
#include <algorithm>
#include <cmath>
#include <numeric>

// container library
#include <array>
#include <bitset>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>

/* ---------- Namespace ---------- */

using namespace std;

/* ---------- Type Abbreviation ---------- */

template <typename T>
using V = vector<T>;
template <typename T, typename U>
using P = pair<T, U>;
template <typename T>
using PQ = priority_queue<T>;
template <typename T>
using GPQ = priority_queue<T, vector<T>, greater<T>>;

using ll = long long;

#define fst first
#define snd second
#define pb push_back
#define mp make_pair
#define mt make_tuple

/* ---------- conversion ---------- */

#define INT(c) static_cast<int>(c)
#define CHAR(n) static_cast<char>(n)
#define LL(n) static_cast<ll>(n)
#define DOUBLE(n) static_cast<double>(n)

/* ---------- container ---------- */

#define ALL(v) (v).begin(), (v).end()
#define SIZE(v) (LL((v).size()))

#define FIND(v, k) (v).find(k) != (v).end()
#define VFIND(v, k) find(ALL(v), k) != (v).end()

#define gsort(b, e) sort(b, e, greater<decltype(*b)>())
#define SORT(v) sort(ALL(v))
#define GSORT(v) gsort(ALL(v))

/* ---------- repetition ---------- */

#define FOR(i, a, b) for (ll i = (a); i < (b); ++i)
#define RFOR(i, a, b) for (ll i = (b)-1; i >= (a); --i)

/* ----------- debug ---------- */

template <class T>
ostream& operator<<(ostream& os, vector<T> v) {
    os << "[";
    for (auto vv : v)
        os << vv << ",";
    return os << "]";
}

template <class T>
ostream& operator<<(ostream& os, set<T> v) {
    os << "[";
    for (auto vv : v)
        os << vv << ",";
    return os << "]";
}

template <class L, class R>
ostream& operator<<(ostream& os, pair<L, R> p) {
    return os << "(" << p.fst << "," << p.snd << ")";
}

/* ---------- Constants ---------- */

// const ll MOD = 1e9 + 7;
// const int INF = 1 << 25;
// const ll INF = 1LL << 50;
// const double PI = acos(-1);
// const double EPS = 1e-10;
// const ll dx[4] = {0, -1, 1, 0};
// const ll dy[4] = {-1, 0, 0, 1};

/* ---------- Short Functions ---------- */

template <typename T>
T sq(T a) {
    return a * a;
}

template <typename T>
T gcd(T a, T b) {
    if (a > b) return gcd(b, a);
    return a == 0 ? b : gcd(b % a, a);
}

template <typename T, typename U>
T mypow(T b, U n) {
    if (n == 0) return 1;
    if (n == 1) return b /* % MOD */;
    if (n % 2 == 0) {
        return mypow(sq(b) /* % MOD */, n / 2);
    } else {
        return mypow(b, n - 1) * b /* % MOD */;
    }
}

ll pcnt(ll b) {
    return __builtin_popcountll(b);
}

/* v-v-v-v-v-v-v-v-v Main Part v-v-v-v-v-v-v-v-v */

// #define DEBUG

V<V<char>> tile(2000, V<char>(2000, '.'));

// 偶数×偶数のグリッドをタイルで埋める
bool tiling(ll N, ll M, ll A, ll B) {
    ll need = (A + 1) / 2 * 4 + (B + 1) / 2 * 4;
    if (N * M < need) return false;

    FOR(i, 0, N / 2) {
        FOR(j, 0, M / 2) {
            FOR(k, 0, 2) {
                if (A == 0) break;
                tile[i * 2 + k][j * 2] = '<';
                tile[i * 2 + k][j * 2 + 1] = '>';
                --A;
            }
        }
    }

    RFOR(i, 0, N / 2) {
        RFOR(j, 0, M / 2) {
            FOR(k, 0, 2) {
                if (B == 0) break;
                tile[i * 2][j * 2 + k] = '^';
                tile[i * 2 + 1][j * 2 + k] = 'v';
                --B;
            }
        }
    }
    return true;
}

// コーナーケースで左下が埋まってるとき専用
bool tiling_corner(ll N, ll M, ll A, ll B) {
    ll need = (A + 1) / 2 * 4 + (B + 1) / 2 * 4;

    // 左下が埋められている分制約が変わる
    if (N * M - 4 < need) return false;

    FOR(i, 0, N / 2) {
        FOR(j, 0, M / 2) {
            // 左下のすでに埋められている箇所は飛ばす
            if (i == N / 2 - 1 && j == 0) continue;

            FOR(k, 0, 2) {
                if (A == 0) break;
                tile[i * 2 + k][j * 2] = '<';
                tile[i * 2 + k][j * 2 + 1] = '>';
                --A;
            }
        }
    }

    RFOR(i, 0, N / 2) {
        RFOR(j, 0, M / 2) {
            // 左下のすでに埋められている箇所は飛ばす
            if (i == N / 2 - 1 && j == 0) continue;

            FOR(k, 0, 2) {
                if (B == 0) break;
                tile[i * 2][j * 2 + k] = '^';
                tile[i * 2 + 1][j * 2 + k] = 'v';
                --B;
            }
        }
    }
    return true;
}

void solve() {
    ll N, M, A, B;
    cin >> N >> M >> A >> B;

    bool res;
    // 敷き詰めが可能か否かを受け取る

    if (N % 2 == 0 && M % 2 == 0) {
        res = tiling(N, M, A, B);

    } else if (N % 2 == 1 && M % 2 == 0) {
        // 一番下の行を埋める
        FOR(j, 0, M / 2) {
            if (A == 0) break;
            tile[N - 1][j * 2] = '<';
            tile[N - 1][j * 2 + 1] = '>';
            --A;
        }
        res = tiling(N - 1, M, A, B);

    } else if (N % 2 == 0 && M % 2 == 1) {
        // 一番右の列を埋める
        FOR(i, 0, N / 2) {
            if (B == 0) break;
            tile[i * 2][M - 1] = '^';
            tile[i * 2 + 1][M - 1] = 'v';
            --B;
        }
        res = tiling(N, M - 1, A, B);

    } else {
        // 一番下の行を埋める
        FOR(j, 0, M / 2) {
            if (A == 0) break;
            tile[N - 1][j * 2 + 1] = '<';
            tile[N - 1][j * 2 + 2] = '>';
            --A;
        }

        // 一番右の列を埋める
        FOR(i, 0, N / 2) {
            if (B == 0) break;
            tile[i * 2][M - 1] = '^';
            tile[i * 2 + 1][M - 1] = 'v';
            --B;
        }

        // 残ったA, Bが共に奇数の場合は特殊処理
        if (A % 2 == 1 && B % 2 == 1) {
            tile[N - 3][0] = '<';
            tile[N - 3][1] = '>';
            tile[N - 2][0] = '^';
            tile[N - 1][0] = 'v';
            --A;
            --B;
            res = tiling_corner(N - 1, M - 1, A, B);
        } else {
            res = tiling(N - 1, M - 1, A, B);
        }
    }

    if (res) {
        cout << "YES" << endl;
        FOR(i, 0, N) {
            FOR(j, 0, M) {
                cout << tile[i][j];
            }
            cout << endl;
        }
    } else {
        cout << "NO" << endl;
    }
    return;
}


/* ---------- ここから下は手を加えないこと ----------- */


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    // cout << fixed << setprecision(10);

#ifdef DEBUG
    freopen("input.txt", "r", stdin);
    int num;
    cin >> num;
    FOR(_, 1, num) {
        cout << "++++++++++++++++++++" << endl;
        solve();
    }
#else
    solve();
#endif

    return 0;
}

Submission Info

Submission Time
Task C - Tiling
User Misteer
Language C++14 (GCC 5.4.1)
Score 900
Code Size 7202 Byte
Status
Exec Time 30 ms
Memory 5248 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 s1.txt, s2.txt, s3.txt
All 900 / 900 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, 49.txt, 50.txt, 51.txt, 52.txt, 53.txt, 54.txt, 55.txt, 56.txt, 57.txt, 58.txt, 59.txt, 60.txt, 61.txt, 62.txt, 63.txt, 64.txt, 65.txt, 66.txt, 67.txt, 68.txt, 69.txt, 70.txt, 71.txt, 72.txt, 73.txt, 74.txt, 75.txt, 76.txt, 77.txt, 78.txt, 79.txt, 80.txt, 81.txt, 82.txt, 83.txt, 84.txt, 85.txt, 86.txt, 87.txt, 88.txt, 89.txt, 90.txt, 91.txt, 92.txt, 93.txt, 94.txt, 95.txt, 96.txt, 97.txt, 98.txt, 99.txt, s1.txt, s2.txt, s3.txt
Case Name Status Exec Time Memory
01.txt 5 ms 4224 KB
02.txt 3 ms 4224 KB
03.txt 4 ms 4224 KB
04.txt 3 ms 4224 KB
05.txt 4 ms 4224 KB
06.txt 4 ms 4224 KB
07.txt 5 ms 4352 KB
08.txt 5 ms 4352 KB
09.txt 3 ms 4224 KB
10.txt 3 ms 4224 KB
11.txt 3 ms 4224 KB
12.txt 3 ms 4224 KB
13.txt 3 ms 4224 KB
14.txt 3 ms 4224 KB
15.txt 13 ms 4608 KB
16.txt 8 ms 4352 KB
17.txt 4 ms 4224 KB
18.txt 7 ms 4352 KB
19.txt 3 ms 4224 KB
20.txt 3 ms 4224 KB
21.txt 9 ms 4480 KB
22.txt 3 ms 4224 KB
23.txt 18 ms 4736 KB
24.txt 12 ms 4608 KB
25.txt 9 ms 4480 KB
26.txt 3 ms 4224 KB
27.txt 6 ms 4352 KB
28.txt 3 ms 4224 KB
29.txt 3 ms 4224 KB
30.txt 3 ms 4224 KB
31.txt 3 ms 4224 KB
32.txt 3 ms 4224 KB
33.txt 27 ms 5120 KB
34.txt 7 ms 4352 KB
35.txt 3 ms 4224 KB
36.txt 3 ms 4224 KB
37.txt 5 ms 4352 KB
38.txt 3 ms 4224 KB
39.txt 3 ms 4224 KB
40.txt 8 ms 4352 KB
41.txt 13 ms 4608 KB
42.txt 6 ms 4352 KB
43.txt 4 ms 4224 KB
44.txt 7 ms 4352 KB
45.txt 14 ms 4608 KB
46.txt 7 ms 4352 KB
47.txt 6 ms 4352 KB
48.txt 8 ms 4480 KB
49.txt 15 ms 4736 KB
50.txt 11 ms 4608 KB
51.txt 3 ms 4224 KB
52.txt 3 ms 4224 KB
53.txt 23 ms 4992 KB
54.txt 17 ms 4736 KB
55.txt 21 ms 4864 KB
56.txt 4 ms 4224 KB
57.txt 7 ms 4352 KB
58.txt 8 ms 4352 KB
59.txt 4 ms 4224 KB
60.txt 3 ms 4224 KB
61.txt 6 ms 4352 KB
62.txt 8 ms 4480 KB
63.txt 19 ms 4864 KB
64.txt 7 ms 4352 KB
65.txt 3 ms 4224 KB
66.txt 3 ms 4224 KB
67.txt 30 ms 5248 KB
68.txt 29 ms 5248 KB
69.txt 30 ms 5248 KB
70.txt 3 ms 4224 KB
71.txt 3 ms 4224 KB
72.txt 3 ms 4224 KB
73.txt 3 ms 4224 KB
74.txt 3 ms 4224 KB
75.txt 3 ms 4224 KB
76.txt 3 ms 4224 KB
77.txt 3 ms 4224 KB
78.txt 30 ms 5248 KB
79.txt 3 ms 4224 KB
80.txt 3 ms 4224 KB
81.txt 3 ms 4224 KB
82.txt 3 ms 4224 KB
83.txt 5 ms 4224 KB
84.txt 4 ms 4224 KB
85.txt 3 ms 4224 KB
86.txt 3 ms 4224 KB
87.txt 3 ms 4224 KB
88.txt 4 ms 4224 KB
89.txt 3 ms 4224 KB
90.txt 3 ms 4224 KB
91.txt 3 ms 4224 KB
92.txt 3 ms 4224 KB
93.txt 3 ms 4224 KB
94.txt 3 ms 4224 KB
95.txt 3 ms 4224 KB
96.txt 3 ms 4224 KB
97.txt 3 ms 4224 KB
98.txt 3 ms 4224 KB
99.txt 3 ms 4224 KB
s1.txt 3 ms 4224 KB
s2.txt 4 ms 4224 KB
s3.txt 3 ms 4224 KB