Submission #1024146

#TimeUsernameProblemLanguageResultExecution timeMemory
1024146LIFSoccer Stadium (IOI23_soccer)C++17
52 / 100
607 ms575068 KiB
#include "soccer.h" #include<bits/stdc++.h> using namespace std; int FF[2005][2005]; bool vis[2005][2005]; int dp[11][11][11][11]; int su[2005][2005]; int n; bool vis2[2005][2005]; struct dg { int prei; int prej; int prec; int pred; }; dg pre[11][11][11][11]; void dfs(int i,int j) { vis[i][j] = true; if(i+1 <= n && vis[i+1][j] == false && FF[i+1][j] == 0)dfs(i+1,j); if(j+1 <= n && vis[i][j+1] == false && FF[i][j+1] == 0)dfs(i,j+1); if(i-1 >= 1 && vis[i-1][j] == false && FF[i-1][j] == 0)dfs(i-1,j); if(j-1 >= 1 && vis[i][j-1] == false && FF[i][j-1] == 0)dfs(i,j-1); return; } struct node { int maxi; int mini; int maxj; int minj; }; node temp; node dfs2(int i,int j) { temp.maxi = max(temp.maxi,i); temp.mini = min(temp.mini,i); temp.maxj = max(temp.maxj,j); temp.minj = min(temp.minj,j); vis2[i][j] = true; if(i+1 <= n && vis2[i+1][j] == false && FF[i+1][j] == 0)dfs2(i+1,j); if(j+1 <= n && vis2[i][j+1] == false && FF[i][j+1] == 0)dfs2(i,j+1); if(i-1 >= 1 && vis2[i-1][j] == false && FF[i-1][j] == 0)dfs2(i-1,j); if(j-1 >= 1 && vis2[i][j-1] == false && FF[i][j-1] == 0)dfs2(i,j-1); return temp; } int biggest_stadium(int N, vector<vector<int>> F) { n = N; for(int i=0;i<F.size();i++) { for(int j=0;j<F[i].size();j++)FF[i+1][j+1] = F[i][j]; } int exis = 0; int ii = -1; int jj = -1; for(int i=1;i<=N;i++) { for(int j=1;j<=N;j++) { su[i][j] = su[i][j-1] + FF[i][j]; if(FF[i][j] == 1) { exis++; ii = i; jj = j; } } } if(N <= 7) { for(int i=1;i<=10;i++) { for(int j=1;j<=10;j++) { for(int k=1;k<=10;k++) { for(int p=1;p<=10;p++)dp[i][j][k][p] = -1e9; } } } vector<node> last; for(int i=1;i<=N;i++) { for(int j=1;j<=N;j++) { if(vis2[i][j] == false && FF[i][j] == 0) { temp.maxi = -1; temp.mini = 1e9; temp.maxj = -1; temp.minj = 1e9; dfs2(i,j); last.push_back(temp); } } } // for(auto it : last)cout<<it.mini<<" "<<it.maxi<<" "<<it.minj<<" "<<it.maxj<<endl; int maxn = -1; for(auto it : last) { for(int len = 1;len <= N;len++) { for(int i=1;i+len-1 <= N;i++) { int j = i+len-1; if(j > it.maxi || i < it.mini)continue; for(int c = 1;c <= N;c++) { for(int d = c;d<=N;d++) //計算dp[i][j][c][d]; { if(c < it.minj || d > it.maxj)continue; for(int e = 1;e<=N;e++) { for(int f = e;f<=N;f++) // 當且僅當e f 可以完全包含c,d: //即e <= c && f >= d { if(e < it.minj || f > it.maxj)continue; if(e > c || f < d)continue; if(i == j) { if(su[i][d] - su[i][c-1] != 0) { dp[i][j][c][d] = - 1e9; } else dp[i][j][c][d] = d - c + 1; } else { if(su[i][d] - su[i][c-1] == 0)//同時,必須保證c,d可以取到 , 即第i行可以取到 { if(dp[i+1][j][e][f] + d - c + 1 >= dp[i][j][c][d]) { dp[i][j][c][d] = max(dp[i][j][c][d],dp[i+1][j][e][f] + d - c + 1); pre[i][j][c][d] = dg{i+1,j,e,f}; } } if(su[j][d] - su[j][c-1] == 0) { if(dp[i][j-1][e][f] + d - c + 1 >= dp[i][j][c][d]) { dp[i][j][c][d] = max(dp[i][j][c][d],dp[i][j-1][e][f] + d - c + 1); pre[i][j][c][d] = dg{i,j-1,e,f}; } } } } } } } } } } for(int i=1;i<=N;i++) { for(int j=1;j<=N;j++) { for(int k=1;k<=N;k++) { for(int p=1;p<=N;p++) { maxn = max(maxn,dp[i][j][k][p]); } } } } int firi = 1; int firj = 7; int firc = 3; int fird = 3; return maxn; } if(exis == 0)return N*N; if(exis == 1) { int ans1 = 0; int ans2 = 0; int ans3 = 0; int ans4 = 0; for(int i=1;i<=N;i++) { for(int j=1;j<=N;j++) { if((j > jj) || (i > ii))ans1++; if((j < jj) || (i < ii))ans2++; if((j > jj) || (i < ii))ans3++; if((j < jj) || (i > ii))ans4++; } } return max(max(ans1,ans2),max(ans3,ans4)); } else { int all = 0; for(int i=1;i<=N;i++) { for(int j=1;j<=N;j++)if(FF[i][j] == 0)all++; } int cnt1 = 0; //第一步,測試是否有多於一個連通塊 for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(vis[i][j] == false && FF[i][j] == 0) { cnt1++; dfs(i,j); } } } if(cnt1 >= 2)return -1; // 即多於一個連通塊,隨便返回 //第二步,測試同一行 / 同一列是否有多於一個連通塊 bool flag2 = true; for(int i=1;i<=N;i++) { int cnt2 = 0; for(int j=1;j<=N;j++) { if(FF[i][j] == 1)continue; while(FF[i][j+1] == 0 && j+1 <= N)j++; cnt2++; if(cnt2 >= 2)flag2 = false; } } if(flag2 == false)return -2; for(int j=1;j<=N;j++) { int cnt2 = 0; for(int i=1;i<=N;i++) { if(FF[i][j] == 1)continue; while(FF[i+1][j] == 0 && i+1 <= N)i++; cnt2++; if(cnt2 >= 2)flag2 = false; } } if(flag2 == false)return -3; //第三步,處理區間; vector<pair<int,int> > row; for(int i=1;i<=N;i++) { for(int j=1;j<=N;j++) { if(FF[i][j] == 1)continue; int fir = j; while(FF[i][j+1] == 0 && j+1 <= N)j++; row.push_back(make_pair(fir,0-j)); } } sort(row.begin(),row.end()); /*for(int i=0;i<row.size();i++)cout<<row[i].first<<" "<<row[i].second<<endl; cout<<endl;*/ bool flag3 = true; for(int i=1;i<row.size();i++) { if((0-row[i].second) > (0-row[i-1].second) && row[i].first != row[i-1].first)flag3 = false; } if(flag3 == false)return -4; vector<pair<int,int> > column; for(int j=1;j<=n;j++) { for(int i=1;i<=n;i++) { if(FF[i][j] == 1)continue; int fir = i; while(FF[i+1][j] == 0 && i+1 <= n)i++; column.push_back(make_pair(fir,0-i)); } } sort(column.begin(),column.end()); bool flag4 = true; for(int i=1;i<column.size();i++) { if((0-column[i].second) > (0-column[i-1].second) && column[i].first != column[i-1].first)flag4 = false; } if(flag4 == false)return -5; return all; } }

Compilation message (stderr)

soccer.cpp: In function 'int biggest_stadium(int, std::vector<std::vector<int> >)':
soccer.cpp:51:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for(int i=0;i<F.size();i++)
      |                 ~^~~~~~~~~
soccer.cpp:53:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         for(int j=0;j<F[i].size();j++)FF[i+1][j+1] = F[i][j];
      |                     ~^~~~~~~~~~~~
soccer.cpp:170:13: warning: unused variable 'firi' [-Wunused-variable]
  170 |         int firi = 1;
      |             ^~~~
soccer.cpp:171:13: warning: unused variable 'firj' [-Wunused-variable]
  171 |         int firj = 7;
      |             ^~~~
soccer.cpp:172:13: warning: unused variable 'firc' [-Wunused-variable]
  172 |         int firc = 3;
      |             ^~~~
soccer.cpp:173:13: warning: unused variable 'fird' [-Wunused-variable]
  173 |         int fird = 3;
      |             ^~~~
soccer.cpp:259:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  259 |         for(int i=1;i<row.size();i++)
      |                     ~^~~~~~~~~~~
soccer.cpp:278:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  278 |         for(int i=1;i<column.size();i++)
      |                     ~^~~~~~~~~~~~~~
#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...