Submission #1225290

#TimeUsernameProblemLanguageResultExecution timeMemory
1225290amine_arouaSoccer Stadium (IOI23_soccer)C++20
3.50 / 100
263 ms48156 KiB
#include "soccer.h" #include<bits/stdc++.h> using namespace std; int cnt = 0 , ret = 0; int xx [] = {-1 , 1 , 0 , 0}; int yy[] = {0 , 0 , -1 , 1}; vector<vector<bool>> vis; vector<vector<int>> grid; int get_nest(pair<int ,int> a , pair<int ,int> b) { if(a.first == b.first && a.second == b.second) return 2; if(a.first <= b.first && b.second <= a.second) return 0; swap(a , b); if(a.first <= b.first && b.second <= a.second) return 1; return -1; } void dfs(int x , int y) { if(vis[x][y]) return ; vis[x][y] = 1; cnt++; for(int k = 0 ; k < 4 ; k++) { int nx = x + xx[k] , ny = y + yy[k]; if(grid[nx][ny] == 0) dfs(nx , ny); } } bool works(int h , int N , vector<vector<int>> &F) { cnt = 0; ret = 0; vis.assign(N + 2 ,vector<bool>(N + 2 , 1)); grid.assign(N + 2 ,vector<int> (N + 2 , 1)); for(int i= 1 ; i <= N ; i++) { for(int j = 1 ; j <= N ; j++) { if(h) grid[j][i] = F[i - 1][j - 1]; else { grid[i][j] = F[i-1][j-1]; } vis[i][j] = 0; ret+=(F[i - 1][j - 1]^1); } } vector<pair<int , int>> v(N + 1); for(int i = 1 ; i <= N ; i++) { int ans = 0; for(int j = 1 ;j <= N+ 1 ; j++) { ans+=(grid[i][j] != grid[i][j - 1]); } if(ans != 2 && ans!= 0) { return 0; } int fr = -1; int lst = -1; for(int j = 1 ; j <= N ; j++) { if(grid[i][j] == 0) { if(fr== -1) fr = j; lst = j; } } v[i] = {fr , lst}; } for(int i = 1 ; i <= N ; i++) { for(int j = 1 ; j <= N ; j++) { if(grid[i][j] == 0) { dfs(i , j); i = N + 1; break; } } } if(cnt != ret) return 0; int lst0 = 0; vector<int> type(N + 1); for(int i = 2 ; i <= N ; i++) { if(v[i].first == -1 || v[i - 1].first == -1) { type[i] = 2; continue; } if(v[i].first == v[i - 1].first && v[i].second == v[i - 1].second) { type[i] = 2; continue; } type[i] = get_nest(v[i] , v[i - 1]); if(type[i] == -1) { return 0; } if(type[i] == 0) lst0 = i; } if(lst0 == 0) { return 1; } int nb1 = count(type.begin() + 2 , type.begin() + lst0+1 , 1); if(nb1) return 0; nb1 = count(type.begin() + 2 , type.end() , 1); if(nb1 == 0) return 1; int fr1 = find(type.begin() + 2 , type.end() , 1) - type.begin(); if(get_nest(v[fr1] , v[lst0 - 1]) == -1) return 0; return 1; } int biggest_stadium(int N, std::vector<std::vector<int>> F) { bool check = (works(0 , N , F)); // cout<<check<<'\n'; if(check) { assert(ret != 0); return ret; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...