제출 #966154

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
966154		Boas	축구 경기장 (IOI23_soccer)	C++17	18 / 100	4539 ms	4184 KiB

soccer

#include "soccer.h"

using namespace std;
#include <bits/stdc++.h>
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;

#define ALL(x) (x).begin(), x.end()
vvi f;
int n;

int TTO(int x, int y)
{
    return y * n + x;
}
ii OTT(int xy)
{
    return {xy % n, xy / n};
}

bool works(const vb &pos)
{
    for (int i = 0; i < n * n; i++)
    {
        if (!pos[i])
            continue;
        for (int j = 0; j < n * n; j++)
        {
            if (!pos[j] || j < i) // remove is problems
                continue;
            auto [x1, y1] = OTT(i);
            auto [x2, y2] = OTT(j);
            if (f[x1][y1] || f[x2][y2])
                throw;
            int x = x1, y = y1;
            bool path1 = true;
            int yD = y2 > y1 ? 1 : -1;
            int xD = x2 > x1 ? 1 : -1;
            while (x != x2)
            {
                x += xD;
                if (f[x][y])
                {
                    path1 = false;
                    break;
                }
            }
            while (path1 && y != y2)
            {
                y += yD;
                if (f[x][y])
                {
                    path1 = false;
                    break;
                }
            }
            if (path1)
                continue;
            x = x1, y = y1;
            while (y != y2)
            {
                y += yD;
                if (f[x][y])
                {
                    return false;
                }
            }
            while (x != x2)
            {
                x += xD;
                if (f[x][y])
                {
                    return false;
                }
            }
        }
    }
    return true;
}

using namespace chrono;

int biggest_stadium(int N, vvi F)
{
    auto t1 = std::chrono::high_resolution_clock::now();
    n = N;
    f = F;
    int trees = 0;
    vector<bool> all(N * N);
    for (int x = 0; x < n; x++)
    {
        for (int y = 0; y < n; y++)
        {
            if (F[x][y])
                trees++;
            else
                all[TTO(x, y)] = 1;
        }
    }
    if (works(all))
        return N * N - trees;
    {
        auto t2 = std::chrono::high_resolution_clock::now();
        std::chrono::duration<double, std::milli> fp_ms = t2 - t1;
        // cerr << fp_ms.count() << endl;
        if (fp_ms.count() > 3000)
            return 1;
    }
    vector<bool> pos(N * N);
    for (int c = N * N - trees; c >= 2; c--)
    {
        pos.assign(N * N, 0);
        for (int i = 0; i < c; i++)
        {
            pos[N * N - 1 - i] = 1;
        }
        do
        {
            auto t2 = std::chrono::high_resolution_clock::now();
            std::chrono::duration<double, std::milli> fp_ms = t2 - t1;
            // cerr << fp_ms.count() << endl;
            if (fp_ms.count() > 2000)
                return 1;
            int posi = true;
            for (int i = 0; i < N * N; i++)
            {
                if (pos[i])
                {
                    auto [x, y] = OTT(i);
                    if (F[x][y])
                    {
                        posi = false;
                        break;
                    }
                }
            }
            if (!posi)
                continue;
            if (works(pos))
                return c;
        } while (next_permutation(ALL(pos)));
    }
    return 1;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 6
• Subtask 2: 8 / 8
• Subtask 3: 5.5 / 22
• Subtask 4: 4.5 / 18
• Subtask 5: 0 / 16
• Subtask 6: 0 / 30