22452023-01-05 13:05:40TuruTamasJardaTcpp11Time limit exceeded 9/40300ms3924 KiB
#include <bits/stdc++.h>
#include <iostream>
using namespace std;

void printTiles(bool * tiles, int N) {
    for (int i = 0; i < N; i++)
    {
        cout << tiles[i * 2] << ' ';
    }
    cout << '\n';
    for (int i = 0; i < N; i++)
    {
        cout << tiles[i * 2 + 1] << ' ';
    }
    cout << '\n';
}

// ha a tilet be lehet illeszteni arra a helyre, akkor beilleszti és return true; ha nem, akkor return false
bool insert_tile(bool * tiles, int loc, int type, int N) {
    // a commentek a tile alakját ábrázolják
    if (tiles[loc]) {
        return false;
    }
    switch (type)
    {
    // L
    case 0:
        if (loc % 2 == 1 || loc / 2 >= N - 1 || tiles[loc + 1] || tiles[loc + 3]) {
            return false;
        }
        else {
            tiles[loc] = true;
            tiles[loc + 1] = true;
            tiles[loc + 3] = true;
        }
    break;
    // __|
    case 1:
        if (loc % 2 == 0 || loc / 2 >= N - 1 || tiles[loc + 1] || tiles[loc + 2]) {
            return false;
        }
        else {
            tiles[loc] = true;
            tiles[loc + 1] = true;
            tiles[loc + 2] = true;
        }
    break;
    // ___
    // |
    case 2:
        if (loc % 2 == 1 || loc / 2 >= N - 1 || tiles[loc + 1] || tiles[loc + 2]) {
            return false;
        }
        else {
            tiles[loc] = true;
            tiles[loc + 1] = true;
            tiles[loc + 2] = true;
        }
    break;
    // __
    //   |
    case 3:
        if (loc % 2 == 1 || loc / 2 >= N - 1 || tiles[loc + 2] || tiles[loc + 3]) {
            return false;
        }
        else {
            tiles[loc] = true;
            tiles[loc + 2] = true;
            tiles[loc + 3] = true;
        }
    break;
    // --
    case 4:
        if (tiles[loc + 2] || loc / 2 >= N - 1) {
            return false;
        }
        else {
            tiles[loc] = true;
            tiles[loc + 2] = true;
        }
    break;
    // |
    case 5:
        if ((loc % 2 == 0 && tiles[loc + 1]) || ((loc % 2 == 1 && tiles[loc - 1]))) {
            return false;
        }
        else {
            tiles[loc] = true;
            if (loc % 2 == 0) {
                tiles[loc + 1] = true;
            }
            else {
                tiles[loc - 1] = true;
            }
        }
    break;
    // T
    case 6:
        if (loc % 2 == 1 || loc / 2 >= N - 2 || tiles[loc + 2] || tiles[loc + 3] || tiles[loc + 4]) {
            return false;
        }
        else {
            tiles[loc] = true;
            fill(tiles + loc + 2, tiles + loc + 5, true);
        }
    break;
    // _|_
    case 7:
        if (loc % 2 == 0 || loc / 2 >= N - 2 || tiles[loc + 1] || tiles[loc + 2] || tiles[loc + 4]) {
            return false;
        }
        else {
            fill(tiles + loc, tiles + loc + 3, true);
            tiles[loc + 4] = true;
        }
    break;
    default:
        throw;
    break;
    }
    return true;
}

void delete_tile(bool * tiles, int loc, int type) {
    // a commentek a tile alakját ábrázolják
    switch (type)
    {
    // L
    case 0:
        tiles[loc] = false;
        tiles[loc + 1] = false;
        tiles[loc + 3] = false;
    break;
    // __|
    case 1:
        tiles[loc] = false;
        tiles[loc + 1] = false;
        tiles[loc + 2] = false;
    break;
    // ___
    // |
    case 2:
        tiles[loc] = false;
        tiles[loc + 1] = false;
        tiles[loc + 2] = false;
    break;
    // __
    //   |
    case 3:
        tiles[loc] = false;
        tiles[loc + 2] = false;
        tiles[loc + 3] = false;
    break;
    // --
    case 4:
        tiles[loc] = false;
        tiles[loc + 2] = false;
    break;
    // |
    case 5:
        tiles[loc] = false;
        if (loc % 2 == 0) {
            tiles[loc + 1] = false;
        }
        else {
            tiles[loc - 1] = false;
        }
    break;
    // T
    case 6:
        tiles[loc] = false;
        fill(tiles + loc + 2, tiles + loc + 5, false);
    break;
    // _|_
    case 7:
        fill(tiles + loc, tiles + loc + 3, false);
        tiles[loc + 4] = false;
    break;
    default:
        throw;
    break;
    }
}

void recurse(bool * tiles, int N, int * r, int first_empty) {
    // cout << '\n';
    // cout.flush();
    // cout << "\n";
    for (int type = 0; type < 8; type++)
    {
        // ha "lyukak" maradnának, akkor continue
        if (first_empty > 1 && (type == 3 || type == 6) && !tiles[first_empty + 1]) {
            continue;
        }
        if (first_empty > 1 && (type == 1 || type == 7) && !tiles[first_empty - 1]) {
            continue;
        }
        if (first_empty > 1 && (type == 0 || type == 2 || type == 5) && (!tiles[first_empty - 1] || !tiles[first_empty - 2])) {
            continue;
        }
        if (first_empty <= 1 && (type == 7 || type == 6 || type == 3 || type == 1)) {
            continue;
        }
        // ha be lehet illeszteni, akkor insert() be is teszi. (thats what she said)
        if (insert_tile(tiles, first_empty, type, N)) {
            // printTiles(tiles, N);
            // cout << '\n';
            int next_empty;
            bool found = false;
            // megkeresi a következő üres részt
            for (int i = first_empty; i < N * 2; i++)
            {
                // cout << i << ' ' << tiles[i] << ' ';
                if (!tiles[i]) {
                    found = true;
                    next_empty = i;
                    break;
                }
            }
            // cerr << '\n' << endl;
            // cout << "\n";
            // cout.flush();
            // cout << endl;
            if (found) {
                // van még üres rész, folytatja onnan
                recurse(tiles, N, r, next_empty);
                delete_tile(tiles, first_empty, type);
            }
            else {
                // nincs több üres rész
                (*r)++;
                if ((*r) == 20200111) {
                    r = 0;
                }
                // cout << "whoo\n";
                delete_tile(tiles, first_empty, type);
                // printTiles(tiles, N);
                // cout << '\n';
            }
            
            
            
        }
    }
}

int main() {
    int N; cin >> N;
    cin.tie(0);
    std::ios_base::sync_with_stdio(1);
    // true: van ott valami
    // false: nincs ott semmi
    // páros a felső sor, páratlan az alsó
        // 0 2 4
        // 1 3 5
    bool * tiles = new bool[N*2];
    fill(tiles, tiles + N*2, false);
    int r = 0;
    recurse(tiles, N, &r, 0);
    cout << r << endl;
}
SubtaskSumTestVerdictTimeMemory
base9/40
1Accepted0/03ms1876 KiB
2Time limit exceeded0/0300ms1968 KiB
3Accepted1/12ms2472 KiB
4Accepted1/12ms2412 KiB
5Accepted2/22ms2448 KiB
6Accepted2/22ms2576 KiB
7Accepted3/33ms2784 KiB
8Time limit exceeded0/3256ms2948 KiB
9Time limit exceeded0/3252ms3160 KiB
10Time limit exceeded0/3280ms2456 KiB
11Time limit exceeded0/3268ms3500 KiB
12Time limit exceeded0/3273ms2880 KiB
13Time limit exceeded0/3246ms3632 KiB
14Time limit exceeded0/3250ms3672 KiB
15Time limit exceeded0/3246ms3924 KiB
16Time limit exceeded0/3273ms3216 KiB
17Time limit exceeded0/4270ms3296 KiB