Submission #456436

#TimeUsernameProblemLanguageResultExecution timeMemory
456436Tenis0206Game (eJOI20_game)C++11
60 / 100
1088 ms332 KiB
#include <bits/stdc++.h> using namespace std; const int oo = 0x3f3f3f3f; int n,m; bool sus[105][105],st[105][105]; int sel[105][105]; bool loop = false; int nr = 0; int cnt = 0; vector<pair<int,int>> c; int p[105]; void Fill(int i, int j, int si, int sj) { ++nr; sel[i][j] = cnt; if(!sus[i][j] && i-1>0) { if(sel[i-1][j]) { if(sel[i-1][j]==cnt && (i-1!=si || j!=sj)) { loop = true; } } else { Fill(i-1,j,i,j); } } if(!sus[i+1][j] && i+1<=n) { if(sel[i+1][j]) { if(sel[i+1][j]==cnt && (i+1!=si || j!=sj)) { loop = true; } } else { Fill(i+1,j,i,j); } } if(!st[i][j] && j-1>0) { if(sel[i][j-1]) { if(sel[i][j-1]==cnt && (i!=si || j-1!=sj)) { loop = true; } } else { Fill(i,j-1,i,j); } } if(!st[i][j+1] && j+1<=m) { if(sel[i][j+1]) { if(sel[i][j+1]==cnt && (i!=si || j+1!=sj)) { loop = true; } return; } else { Fill(i,j+1,i,j); } } } int Back(int k, bool turn, int last) { bool done1 = false, done2 = false; if(turn==1) { int Max = -oo; for(int i=0;i<c.size();i++) { if(i>0 && c[i]==c[i-1] && p[i]==p[i-1]) { continue; } if(c[i].second==true) { if(p[i]==0 && last) { p[i] = 1; Max = max(Max,Back(k+1,0,0)); p[i] = 0; } else if(p[i]==1) { p[i] = 3; Max = max(Max,Back(k+1,1,1)+c[i].first); p[i] = 1; if(c[i].first>4) { p[i] = 2; Max = max(Max,Back(k+1,0,1)+c[i].first-4); p[i] = 1; } } else if(p[i]==2 && !done2) { done2 = true; p[i] = 3; Max = max(Max,Back(k+1,1,1)+4); p[i] = 2; } } else { if(p[i]==0 && last) { p[i] = 1; Max = max(Max,Back(k+1,0,0)); p[i] = 0; } else if(p[i]==1) { p[i] = 3; Max = max(Max,Back(k+1,1,1)+c[i].first); p[i] = 1; if(c[i].first>2) { p[i] = 2; Max = max(Max,Back(k+1,0,1)+c[i].first-2); p[i] = 1; } } else if(p[i]==2 && !done1) { done1 = true; p[i] = 3; Max = max(Max,Back(k+1,1,1)+2); p[i] = 2; } } } if(Max==-oo) { Max = 0; } return Max; } else { int Min = oo; for(int i=0;i<c.size();i++) { if(i>0 && c[i]==c[i-1] && p[i]==p[i-1]) { continue; } if(c[i].second==true) { if(p[i]==0 && last) { p[i] = 1; Min = min(Min,Back(k+1,1,0)); p[i] = 0; } else if(p[i]==1) { p[i] = 3; Min = min(Min,Back(k+1,0,1)-c[i].first); p[i] = 1; if(c[i].first>4) { p[i] = 2; Min = min(Min,Back(k+1,1,1)-(c[i].first-4)); p[i] = 1; } } else if(p[i]==2 && !done2) { done2 = true; p[i] = 3; Min = min(Min,Back(k+1,0,1)-4); p[i] = 2; } } else { if(p[i]==0 && last) { p[i] = 1; Min = min(Min,Back(k+1,1,0)); p[i] = 0; } else if(p[i]==1) { p[i] = 3; Min = min(Min,Back(k+1,0,1)-c[i].first); p[i] = 1; if(c[i].first>2) { p[i] = 2; Min = min(Min,Back(k+1,1,1)-(c[i].first-2)); p[i] = 1; } } else if(p[i]==2 && !done1) { done1 = true; p[i] = 3; Min = min(Min,Back(k+1,0,1)-2); p[i] = 2; } } } if(Min==oo) { Min = 0; } return Min; } } void debug(vector<pair<int,int>> v) { for(auto it : v) { cerr<<it.first<<' '<<it.second<<'\n'; } } int main() { ios::sync_with_stdio(false); cin.tie(0); cin>>n>>m; for(int i=1; i<=n+1; i++) { for(int j=1; j<=m; j++) { char ch; cin>>ch; sus[i][j] = ch-'0'; } } for(int i=1; i<=n; i++) { for(int j=1; j<=m+1; j++) { char ch; cin>>ch; st[i][j] = ch-'0'; } } for(int i=1; i<=n; i++) { for(int j=1; j<=m; j++) { if(sus[i][j] && sus[i+1][j] && st[i][j] && st[i][j+1]) { sel[i][j] = -1; continue; } if(sel[i][j]) { continue; } nr = 0; ++cnt; loop = false; Fill(i,j,0,0); c.push_back({nr,loop}); } } sort(c.begin(),c.end()); cout<<Back(1,1,-1)<<'\n'; return 0; }

Compilation message (stderr)

game.cpp: In function 'int Back(int, bool, int)':
game.cpp:81: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]
   81 |         for(int i=0;i<c.size();i++)
      |                     ~^~~~~~~~~
game.cpp:153: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]
  153 |         for(int i=0;i<c.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...