제출 #980208

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
980208		vjudge1	축구 경기장 (IOI23_soccer)	C++17	8 / 100	4172 ms	23160 KiB

soccer

#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector <int>;
using vvi = vector <vi>;
using vll = vector <ll>;

map <int, ll> mp = 
{{1, 1}, {2, 1}, {3, 1}, {4, 1}, {6, 1}, {7, 1},
{8, 1}, {9, 1}, {11, 1}, {15, 1}, {16, 1}, {18, 1},
{19, 1}, {22, 1}, {23, 1}, {24, 1}, {25, 1}, {26, 1},
{27, 1}, {30, 0}, {31, 1}, {32, 1}, {36, 1}, {38, 1},
{39, 1}, {47, 0}, {48, 1}, {50, 1}, {51, 0}, {52, 1},
{54, 1}, {55, 1}, {56, 1}, {57, 1}, {58, 1}, {59, 1},
{60, 1}, {61, 0}, {62, 1}, {63, 1}, {64, 1}, {72, 1},
{73, 1}, {75, 1}, {79, 1}, {88, 1}, {89, 1}, {90, 0},
{91, 1}, {94, 0}, {95, 1}, {111, 0}, {120, 1}, {121, 1},
{122, 0}, {123, 1}, {124, 0}, {125, 0}, {126, 0}, {127, 1},
{128, 1}, {144, 1}, {146, 1}, {147, 1}, {150, 1}, {151, 1},
{152, 1}, {153, 0}, {154, 1}, {155, 1}, {158, 0}, {159, 1},
{176, 1}, {178, 1}, {179, 0}, {180, 0}, {182, 1}, {183, 1},
{184, 1}, {185, 0}, {186, 1}, {187, 1}, {188, 0}, {189, 0},
{190, 1}, {191, 1}, {192, 1}, {200, 1}, {201, 1}, {203, 0},
{207, 0}, {208, 1}, {210, 1}, {211, 0}, {214, 0}, {215, 0},
{216, 1}, {217, 1}, {218, 1}, {219, 1}, {222, 0}, {223, 1},
{239, 0}, {240, 0}, {242, 0}, {243, 0}, {244, 0}, {246, 0},
{247, 0}, {248, 1}, {249, 1}, {250, 1}, {251, 1}, {252, 0},
{253, 0}, {254, 0}, {255, 1}, {256, 1}, {288, 1}, {292, 1},
{294, 1}, {295, 1}, {303, 0}, {304, 1}, {306, 0}, {307, 0},
{308, 1}, {310, 1}, {311, 1}, {312, 1}, {313, 0}, {314, 0},
{315, 0}, {316, 1}, {317, 0}, {318, 1}, {319, 1}, {367, 0},
{376, 0}, {377, 0}, {378, 0}, {379, 0}, {380, 0}, {381, 0},
{382, 0}, {383, 0}, {384, 1}, {400, 1}, {402, 1}, {403, 0},
{406, 0}, {407, 0}, {408, 0}, {409, 0}, {410, 0}, {411, 0},
{414, 0}, {415, 0}, {416, 1}, {420, 1}, {422, 0}, {423, 0},
{431, 0}, {432, 1}, {434, 1}, {435, 0}, {436, 1}, {438, 1},
{439, 1}, {440, 1}, {441, 0}, {442, 1}, {443, 0}, {444, 1},
{445, 0}, {446, 1}, {447, 1}, {448, 1}, {456, 1}, {457, 1},
{459, 0}, {463, 0}, {464, 1}, {466, 1}, {467, 0}, {470, 0},
{471, 0}, {472, 1}, {473, 1}, {474, 1}, {475, 1}, {478, 0},
{479, 0}, {480, 1}, {484, 1}, {486, 0}, {487, 0}, {488, 0},
{489, 0}, {491, 0}, {492, 0}, {493, 0}, {494, 0}, {495, 0},
{496, 1}, {498, 1}, {499, 0}, {500, 1}, {502, 1}, {503, 0},
{504, 1}, {505, 1}, {506, 1}, {507, 1}, {508, 1}, {509, 0},
{510, 1}, {511, 1}};

int biggest_stadium (int n, vvi f) {
    ll ans = 0;
    for (int mask = 0; mask < (1<<(n*n)); mask++) {
        bool th[n][n];
        bool unval = false;
        ll si = -16, sj;
        for (ll i = 0; i < n; i++) {
            for (ll j = 0; j < n; j++) {
                th[i][j] = mask>>(n*i+j)&1;
                if (th[i][j]) {
                    si = i;
                    sj = j;
                }
                if (th[i][j] && f[i][j]) { unval = true; break; }
            }
        }
        unval |= si == -16;
        if (unval) continue;
        queue <ll> q;
        q.push(si);
        q.push(sj);
        vector <vector <char> > vis(n, vector <char> (n, false));
        ll c = 0;
        while (q.size()) {
            ll i = q.front(); q.pop();
            ll j = q.front(); q.pop();
            if (f[i][j]) continue;
            if (!th[i][j]) continue;
            if (vis[i][j]) continue;
            vis[i][j] = true;
            c++;
            if (i > 0) {
                q.push(i-1);
                q.push(j);
            }
            if (j > 0) {
                q.push(i);
                q.push(j-1);
            }
            if (i < n-1) {
                q.push(i+1);
                q.push(j);
            }
            if (j < n-1) {
                q.push(i);
                q.push(j+1);
            }
        }
        if (c != __builtin_popcount(mask)) continue;
        if (mp[mask]) ans = max(ans, ll(__builtin_popcount(mask)));
    }
    return int(ans);
}

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