oj.uz

Submission #980223

# Submission time Handle Problem Language Result Execution time Memory
980223 2024-05-12T01:21:01 Z vjudge1 Soccer Stadium (IOI23_soccer) C++17
14 / 100
 261 ms 31772 KB 
    #include "soccer.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define deb(x) cout<<#x<<": "<<x<<endl;
int biggest_stadium(int N, vector<vector<int>> F)
{
    if(N>3){
int numoftree=0;
 for(int i=0; i<N; ++i){
    for(int j=0; j<N; ++j){
        if(F[i][j]==1){
            numoftree++;
        }
    }
 }
if(numoftree<=1){
 for(int i=0; i<N; ++i){
    for(int j=0; j<N; ++j){
        if(F[i][j]==1){
            int ans=min((i+1)*(j+1), (N-i)*(j+1));
            ans=min(ans, (i+1)*(N-j));
            ans=min(ans, (N-i)*(N-j));
            ans=N*N-ans;
            return ans;
        }
    }
 }
 return N*N;
    }
    else{

        bool jala=true;
        for(int i=0; i<N && jala; ++i){
            int notree=0;
            int tree=0;
            for(int j=0; j<N && jala; ++j){
                if(F[i][j]==1){
                  if(notree>0) tree++;
                }
                else{
                    if(notree>0 && tree>0){
                        jala=false;
                    }
                    notree++;
                }
            }
        }
         for(int i=0; i<N && jala; ++i){
            int notree=0;
            int tree=0;
            for(int j=0; j<N && jala; ++j){
                if(F[j][i]==1){
                   if(notree>0) tree++;
                }
                else{
                    if(notree>0 && tree>0){
                        jala=false;
                    }
                    notree++;
                }
            }
        }

        queue<pair<int,int>> q;
        for(int i=0; i<N && q.empty(); ++i){
            for(int j=0; j<N && q.empty(); ++j){
                if(F[i][j]==0){
                    q.push({i,j});
                }
            }
        }
        while(!q.empty()){
            int a=q.front().first;
            int b=q.front().second;
            q.pop();
            if(F[a][b]==2) continue;
            F[a][b]=2;
            if(b-1>=0 && F[a][b-1]==0){
                F[a][b-1]=-1;
                q.push({a, b-1});
            }
            if(a-1>=0 && F[a-1][b]==0){
                F[a-1][b]=-1;
                q.push({a-1, b});
            }
            if(b+1<N && F[a][b+1]==0){
                F[a][b+1]=-1;
                q.push({a, b+1});
            }
            if(a+1<N && F[a+1][b]==0){
                F[a+1][b]=-1;
                q.push({a+1, b});
            }
            
        }
        for(int i=0; i<N && jala; ++i){
            for(int j=0; j<N && jala; ++j){
                if(F[i][j]==0){
                    jala=false;
                }
            }
        }

        if(jala){
            return N*N-numoftree;
        }
        else{
            return N*N-numoftree+1;
        }
    }
    }
    int ans=0;
    int ayuda=N*N;
    int mevoyamorir=pow(2, ayuda);
    
    for(int mask=0;mask < mevoyamorir; ++mask){
        vector<vector<int>> grid (N, vector<int> (N, 0));
        for(int i=0; i<N; ++i){
            for(int j=0; j<N; ++j){
                if(F[i][j]==1){
                    grid[i][j]=-1;
                }
            }
        }
        int aux=mask;
    	int col=0;
        int fil=0;
        vector<pair<int,int>> coord;
        while(aux>0){
            if(aux%2){
                if(grid[fil][col]==-1){
                    break;
                }
                grid[fil][col]=1;
                coord.pb({fil, col});
            }
            col++;
            if(col>=N){
                fil++;
                col=0;
            }
            aux/=2;
        }
        if(aux>0){
            continue;
        }
        bool posib=true;

        for(int i=0; i<coord.size(); ++i){
            for(int j=i+1; j<coord.size(); ++j){
                if(grid[coord[i].first][coord[j].second]==1 || grid[coord[j].first][coord[i].second]==1){
                    if(coord[i].first==coord[j].first){
                        int a=coord[i].second;
                        int b=coord[j].second;
                        if(a>b) swap(a,b);
                        for(int x=a; x<=b; ++x){
                            if(grid[coord[i].first][x]!=1){
                                posib=false;
                                break;
                            }
                        } 
                        if(!posib) break;
                    }
                    if(coord[i].second==coord[j].second){
                        int a=coord[i].first;
                        int b=coord[j].first;
                        if(a>b) swap(a,b);
                        for(int x=a; x<=b; ++x){
                            if(grid[x][coord[i].second]!=1){
                                posib=false;
                                break;
                            }
                        } 
                        if(!posib) break;
                    }
                }
                else{
                    posib=false;
                    break;
                }
            }
            if(!posib) break;
        }
        if(posib){

            ans=max(ans,(int) coord.size());
        }

    }
    return ans;
}

Compilation message

soccer.cpp: In function 'int biggest_stadium(int, std::vector<std::vector<int> >)':
soccer.cpp:150:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |         for(int i=0; i<coord.size(); ++i){
      |                      ~^~~~~~~~~~~~~
soccer.cpp:151:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  151 |             for(int j=i+1; j<coord.size(); ++j){
      |                            ~^~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 348 KB partial

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB ok
2 Correct 1 ms 504 KB ok
3 Correct 1 ms 600 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 1 ms 408 KB ok
7 Correct 1 ms 348 KB ok
8 Correct 16 ms 2396 KB ok
9 Correct 261 ms 31772 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB ok
2 Correct 1 ms 504 KB ok
3 Correct 1 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 1 ms 348 KB ok
6 Correct 1 ms 348 KB ok
7 Correct 1 ms 348 KB ok
8 Correct 1 ms 600 KB ok
9 Correct 1 ms 348 KB ok
10 Correct 1 ms 348 KB ok
11 Correct 1 ms 348 KB ok
12 Correct 1 ms 768 KB ok
13 Correct 1 ms 348 KB ok

Subtask #3
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 348 KB partial
2 Correct 1 ms 348 KB ok
3 Correct 1 ms 504 KB ok
4 Correct 1 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 1 ms 348 KB ok
7 Correct 1 ms 348 KB ok
8 Correct 1 ms 348 KB ok
9 Correct 1 ms 600 KB ok
10 Correct 1 ms 348 KB ok
11 Correct 1 ms 348 KB ok
12 Correct 1 ms 348 KB ok
13 Correct 1 ms 768 KB ok
14 Correct 1 ms 348 KB ok
15 Partially correct 1 ms 348 KB partial
16 Partially correct 1 ms 348 KB partial
17 Partially correct 1 ms 344 KB partial
18 Partially correct 1 ms 348 KB partial
19 Partially correct 0 ms 344 KB partial
20 Correct 1 ms 348 KB ok
21 Correct 0 ms 348 KB ok
22 Incorrect 1 ms 348 KB wrong
23 Halted 0 ms 0 KB -

Subtask #4
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 348 KB partial
2 Correct 1 ms 348 KB ok
3 Correct 1 ms 504 KB ok
4 Correct 1 ms 600 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 1 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 1 ms 348 KB ok
9 Correct 1 ms 348 KB ok
10 Correct 1 ms 348 KB ok
11 Correct 1 ms 600 KB ok
12 Correct 1 ms 348 KB ok
13 Correct 1 ms 348 KB ok
14 Correct 1 ms 348 KB ok
15 Correct 1 ms 768 KB ok
16 Correct 1 ms 348 KB ok
17 Partially correct 1 ms 348 KB partial
18 Partially correct 1 ms 348 KB partial
19 Partially correct 1 ms 344 KB partial
20 Partially correct 1 ms 348 KB partial
21 Partially correct 0 ms 344 KB partial
22 Correct 1 ms 348 KB ok
23 Correct 0 ms 348 KB ok
24 Incorrect 1 ms 348 KB wrong
25 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 348 KB partial
2 Correct 1 ms 348 KB ok
3 Correct 1 ms 504 KB ok
4 Correct 1 ms 600 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 1 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 1 ms 348 KB ok
9 Correct 1 ms 348 KB ok
10 Correct 1 ms 348 KB ok
11 Correct 1 ms 600 KB ok
12 Correct 1 ms 348 KB ok
13 Correct 1 ms 348 KB ok
14 Correct 1 ms 348 KB ok
15 Correct 1 ms 768 KB ok
16 Correct 1 ms 348 KB ok
17 Partially correct 1 ms 348 KB partial
18 Partially correct 1 ms 348 KB partial
19 Partially correct 1 ms 344 KB partial
20 Partially correct 1 ms 348 KB partial
21 Partially correct 0 ms 344 KB partial
22 Correct 1 ms 348 KB ok
23 Correct 0 ms 348 KB ok
24 Incorrect 1 ms 348 KB wrong
25 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 348 KB partial
2 Correct 1 ms 348 KB ok
3 Correct 1 ms 504 KB ok
4 Correct 1 ms 600 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 1 ms 408 KB ok
8 Correct 1 ms 348 KB ok
9 Correct 16 ms 2396 KB ok
10 Correct 261 ms 31772 KB ok
11 Correct 1 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 1 ms 348 KB ok
14 Correct 1 ms 348 KB ok
15 Correct 1 ms 348 KB ok
16 Correct 1 ms 600 KB ok
17 Correct 1 ms 348 KB ok
18 Correct 1 ms 348 KB ok
19 Correct 1 ms 348 KB ok
20 Correct 1 ms 768 KB ok
21 Correct 1 ms 348 KB ok
22 Partially correct 1 ms 348 KB partial
23 Partially correct 1 ms 348 KB partial
24 Partially correct 1 ms 344 KB partial
25 Partially correct 1 ms 348 KB partial
26 Partially correct 0 ms 344 KB partial
27 Correct 1 ms 348 KB ok
28 Correct 0 ms 348 KB ok
29 Incorrect 1 ms 348 KB wrong
30 Halted 0 ms 0 KB -