oj.uz

Submission #1064231

# Submission time Handle Problem Language Result Execution time Memory
1064231 2024-08-18T10:40:25 Z parsadox2 Soccer Stadium (IOI23_soccer) C++17
13.5 / 100
 2529 ms 66184 KB 
#include "soccer.h"
#include <bits/stdc++.h>

#define F first
#define S second

using namespace std;

const int N = 50;
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;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2353 ms 65876 KB ok

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2442 ms 65872 KB ok
2 Correct 2422 ms 65976 KB ok
3 Runtime error 1 ms 348 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2442 ms 65872 KB ok
2 Correct 2422 ms 65976 KB ok
3 Correct 2483 ms 65996 KB ok
4 Correct 2508 ms 65984 KB ok
5 Correct 2491 ms 66016 KB ok
6 Correct 2516 ms 66016 KB ok
7 Correct 2460 ms 65864 KB ok
8 Correct 2456 ms 65860 KB ok
9 Correct 2422 ms 66072 KB ok
10 Correct 2529 ms 66008 KB ok
11 Correct 2491 ms 66024 KB ok
12 Correct 2456 ms 65872 KB ok
13 Correct 2515 ms 66044 KB ok

Subtask #3
5.5 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2353 ms 65876 KB ok
2 Correct 2442 ms 65872 KB ok
3 Correct 2422 ms 65976 KB ok
4 Correct 2483 ms 65996 KB ok
5 Correct 2508 ms 65984 KB ok
6 Correct 2491 ms 66016 KB ok
7 Correct 2516 ms 66016 KB ok
8 Correct 2460 ms 65864 KB ok
9 Correct 2456 ms 65860 KB ok
10 Correct 2422 ms 66072 KB ok
11 Correct 2529 ms 66008 KB ok
12 Correct 2491 ms 66024 KB ok
13 Correct 2456 ms 65872 KB ok
14 Correct 2515 ms 66044 KB ok
15 Partially correct 2370 ms 65960 KB partial
16 Partially correct 2300 ms 65872 KB partial
17 Correct 2299 ms 65988 KB ok
18 Correct 2328 ms 66076 KB ok
19 Correct 2306 ms 66008 KB ok
20 Correct 2415 ms 65936 KB ok
21 Correct 2245 ms 65928 KB ok
22 Correct 2243 ms 65976 KB ok
23 Correct 2209 ms 65872 KB ok
24 Correct 2307 ms 65876 KB ok
25 Correct 2239 ms 66184 KB ok
26 Correct 2306 ms 65876 KB ok

Subtask #4
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2353 ms 65876 KB ok
2 Correct 2442 ms 65872 KB ok
3 Correct 2422 ms 65976 KB ok
4 Runtime error 1 ms 348 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2353 ms 65876 KB ok
2 Correct 2442 ms 65872 KB ok
3 Correct 2422 ms 65976 KB ok
4 Runtime error 1 ms 348 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2353 ms 65876 KB ok
2 Correct 2442 ms 65872 KB ok
3 Correct 2422 ms 65976 KB ok
4 Runtime error 1 ms 348 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -