| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 457709 |
2021-08-07T10:10:10 Z |
Tenis0206 |
Game (eJOI20_game) |
C++11 |
|
3 ms |
332 KB |
#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 rez[2][1000005];
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 turn, int state)
{
if(turn)
{
int Max = -oo;
for(int i=0; i<c.size(); i++)
{
if((state&(1<<i))!=0)
{
continue;
}
int Min = oo;
int new_state = state + (1<<i);
if(rez[0][new_state]!=oo)
{
Min = min(Min,rez[0][new_state] - c[i].first);
}
else
{
Min = min(Min,Back(0,new_state) - c[i].first);
}
if(c[i].second==false && c[i].first>2)
{
if(rez[1][new_state]!=oo)
{
Min = min(Min,rez[1][new_state] - c[i].first + 4);
}
else
{
Min = min(Min,Back(1,new_state) - c[i].first + 4);
}
}
if(c[i].second==true)
{
if(rez[1][new_state]!=oo)
{
Min = min(Min,rez[1][new_state] - c[i].first + 8);
}
else
{
Min = min(Min,Back(1,new_state) - c[i].first + 8);
}
}
Max = max(Max,Min);
}
if(Max==-oo)
{
Max = 0;
}
rez[1][state] = Max;
return Max;
}
else
{
int Min = oo;
for(int i=0;i<c.size();i++)
{
if((state&(1<<i))!=0)
{
continue;
}
int Max = -oo;
int new_state = state + (1<<i);
if(rez[1][new_state]!=oo)
{
Max = max(Max,rez[1][new_state] + c[i].first);
}
else
{
Max = max(Max,Back(1,new_state) + c[i].first);
}
if(c[i].second==false && c[i].first>2)
{
if(rez[0][new_state]!=oo)
{
Max = max(Max,rez[0][new_state] + c[i].first - 4);
}
else
{
Max = max(Max,Back(0,new_state) + c[i].first - 4);
}
}
if(c[i].second==true)
{
if(rez[0][new_state]!=oo)
{
Max = max(Max,rez[0][new_state] + c[i].first - 8);
}
else
{
Max = max(Max,Back(0,new_state) + c[i].first - 8);
}
}
Min = min(Min,Max);
}
if(Min==oo)
{
Min = 0;
}
rez[0][state] = Min;
return Min;
}
}
void debug(vector<pair<int,int>> v)
{
for(auto it : v)
{
cerr<<it.first<<' '<<it.second<<'\n';
}
}
int main()
{
freopen("nr.in","r",stdin);
freopen("nr.out","w",stdout);
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});
}
}
for(int i=0;i<(1<<(c.size()));i++)
{
rez[0][i] = rez[1][i] = oo;
}
cout<<Back(1,0)<<'\n';
return 0;
}
Compilation message
game.cpp: In function 'int Back(int, int)':
game.cpp:80: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]
80 | for(int i=0; i<c.size(); i++)
| ~^~~~~~~~~
game.cpp:130: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]
130 | for(int i=0;i<c.size();i++)
| ~^~~~~~~~~
game.cpp: In function 'int main()':
game.cpp:187:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
187 | freopen("nr.in","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~
game.cpp:188:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
188 | freopen("nr.out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
