Submission #1064238

# Submission time Handle Problem Language Result Execution time Memory
1064238 2024-08-18T10:43:34 Z parsadox2 Soccer Stadium (IOI23_soccer) C++17
13.5 / 100
2522 ms 66072 KB
#include "soccer.h"
#include <bits/stdc++.h>

#define F first
#define S second

using namespace std;

const int N = 50 + 10;
int n;
vector<vector<int>> a;
bool adj[N][N];
bool all[2][(1 << 25)];
int bad_adj[N];

int f(pair<int , int> v)
{
    return v.F * n + v.S;
}

void Add_Edge(pair <int , int> u , pair<int , int> v)
{
    if(a[u.F][u.S] == 1 || a[v.F][v.S] == 1)
        return;
    pair <int , int> x , y;
    x = make_pair(u.F , v.S);
    int ans1 = a[x.F][x.S];
    y = make_pair(v.F , u.S);
    int ans2 = a[y.F][y.S];
    //cout << "____________" << endl;
    for(int i = u.S ; i >= x.S ; i--)
    {
        //cout << 1 << " : " << u.F << " " << i << endl;
        ans1 += a[u.F][i];
    }
    for(int i = u.S ; i <= x.S ; i++)
    {
        //cout << 1 << " : " << u.F << " " << i << endl;
        ans1 += a[u.F][i];
    }
    for(int i = v.S ; i >= y.S ; i--)
    {
        //cout << 2 << " : " << v.F << " " << i << endl;
        ans2 += a[v.F][i];
    }
    for(int i = v.S ; i <= y.S ; i++)
    {
        //cout << 2 << " : " << v.F << " " << i << endl;
        ans2 += a[v.F][i];
    }

    for(int i = u.F ; i >= y.F ; i--)
    {
        //cout << 2 << " : " << i << " " << u.S << endl;
        ans2 += a[i][u.S];
    }
    for(int i = u.F ; i <= y.F ; i++)
    {
        //cout << 1 << " : " << i << " " << u.S << endl;
        ans2 += a[i][u.S];
    }
    for(int i = v.F ; i >= x.F ; i--)
    {
        //cout << 2 << " : " << i << " " << v.S << endl;
        ans1 += a[i][v.S];
    }
    for(int i = v.F ; i <= x.F ; i++)
    {
        //cout << 2 << " : " << i << " " << v.S << endl;
        ans1 += a[i][v.S];
    }

    if(ans1 == 0 || ans2 == 0)
        adj[f(u)][f(v)] = adj[f(v)][f(u)] = true;
}

int biggest_stadium(int nn, vector<std::vector<int>> F)
{
    n = nn;
    a = F;
    for(int i = 0 ; i < n ; i++)  for(int j = 0 ; j < n ; j++)  for(int ii = 0 ; ii < n ; ii++)  for(int jj = 0 ; jj < n ; jj++)
    {
        Add_Edge(make_pair(i , j) , make_pair(ii , jj));
    }
    all[0][0] = all[1][0] = true;
    int ans = 0;
    for(int mask = 1 ; mask < (1 << 25) ; mask++)
    {
        int fir = 0;
        for(int i = 0 ; i < 25 ; i++)  if((mask >> i) & 1)
        {
            fir = i;
            break;
        }
        all[0][mask] = all[0][(mask ^ (1 << fir))];
        all[1][mask] = all[1][(mask ^ (1 << fir))];
        for(int i = fir ; i < 25 ; i++)  if((mask >> i) & 1)
        {
            if(!adj[fir][i])
                all[0][mask] = false;
            if(!adj[fir + 25][i + 25])
                all[1][mask] = false;
        }
        if(all[0][mask] || all[1][mask])
            ans = max(ans , __builtin_popcount(mask));
    }
    for(int i = 25 ; i <= 50 ; i++)  for(int j = 0 ; j < 25 ; j++)  if(adj[i][j])
        bad_adj[i] |= (1 << j);
    for(int mask = 0 ; mask < (1 << 25) ; mask++)  if(all[1][mask])
    {
        int tmp = (1 << 25) - 1;
        for(int i = 0 ; i < 25 ; i++)  if((mask >> i) & 1)
            tmp &= bad_adj[i + 25];
        if(all[0][tmp])
            ans = max(ans , __builtin_popcount(mask) + __builtin_popcount(tmp));
    }
    return ans;
}
# Verdict Execution time Memory Grader output
1 Correct 2365 ms 65876 KB ok
# Verdict Execution time Memory Grader output
1 Correct 2369 ms 66072 KB ok
2 Correct 2379 ms 65872 KB ok
3 Runtime error 1 ms 344 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 2369 ms 66072 KB ok
2 Correct 2379 ms 65872 KB ok
3 Correct 2480 ms 65876 KB ok
4 Correct 2522 ms 65872 KB ok
5 Correct 2444 ms 65872 KB ok
6 Correct 2506 ms 65996 KB ok
7 Correct 2496 ms 66072 KB ok
8 Correct 2463 ms 65980 KB ok
9 Correct 2341 ms 66012 KB ok
10 Correct 2473 ms 66016 KB ok
11 Correct 2465 ms 66056 KB ok
12 Correct 2498 ms 66064 KB ok
13 Correct 2460 ms 66016 KB ok
# Verdict Execution time Memory Grader output
1 Correct 2365 ms 65876 KB ok
2 Correct 2369 ms 66072 KB ok
3 Correct 2379 ms 65872 KB ok
4 Correct 2480 ms 65876 KB ok
5 Correct 2522 ms 65872 KB ok
6 Correct 2444 ms 65872 KB ok
7 Correct 2506 ms 65996 KB ok
8 Correct 2496 ms 66072 KB ok
9 Correct 2463 ms 65980 KB ok
10 Correct 2341 ms 66012 KB ok
11 Correct 2473 ms 66016 KB ok
12 Correct 2465 ms 66056 KB ok
13 Correct 2498 ms 66064 KB ok
14 Correct 2460 ms 66016 KB ok
15 Partially correct 2513 ms 66068 KB partial
16 Partially correct 2380 ms 66020 KB partial
17 Correct 2340 ms 65876 KB ok
18 Correct 2284 ms 66040 KB ok
19 Correct 2340 ms 65884 KB ok
20 Correct 2422 ms 65916 KB ok
21 Correct 2325 ms 65844 KB ok
22 Correct 2240 ms 65872 KB ok
23 Correct 2215 ms 65856 KB ok
24 Correct 2352 ms 66032 KB ok
25 Correct 2239 ms 65880 KB ok
26 Correct 2341 ms 65980 KB ok
# Verdict Execution time Memory Grader output
1 Correct 2365 ms 65876 KB ok
2 Correct 2369 ms 66072 KB ok
3 Correct 2379 ms 65872 KB ok
4 Runtime error 1 ms 344 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 2365 ms 65876 KB ok
2 Correct 2369 ms 66072 KB ok
3 Correct 2379 ms 65872 KB ok
4 Runtime error 1 ms 344 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 2365 ms 65876 KB ok
2 Correct 2369 ms 66072 KB ok
3 Correct 2379 ms 65872 KB ok
4 Runtime error 1 ms 344 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -