| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 456470 |
2021-08-06T21:14:06 Z |
Tenis0206 |
Game (eJOI20_game) |
C++11 |
|
1 ms |
204 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;
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)
{
if(k==c.size())
{
return 0;
}
if(turn)
{
int Min = oo;
if(c[k].second==true && c[k].first>4)
{
Min = min(Min,Back(k+1,1) - c[k].first + 8);
}
if(c[k].second==false && c[k].first>2)
{
Min = min(Min,Back(k+1,1) - c[k].first + 4);
}
Min = min(Min,Back(k+1,0) - c[k].first);
return Min;
}
else
{
int Max = -oo;
if(c[k].second==true && c[k].first>4)
{
Max = max(Max,Back(k+1,0) + c[k].first - 8);
}
if(c[k].second==false && c[k].first>2)
{
Max = max(Max,Back(k+1,0) + c[k].first - 4);
}
Max = max(Max,Back(k+1,1) + c[k].first);
return Max;
}
}
bool cmp(pair<int,int> a, pair<int,int> b)
{
if(a.second==b.second)
{
return a.first<b.first;
}
bool ok1 = false, ok2 = false;
if((a.second==false && a.first>2) || (a.second==true && a.first>4))
{
ok1 = true;
}
if((b.second==false && b.first>2) || (b.second==true && b.first>4))
{
ok2 = true;
}
if(ok1 && ok2)
{
return a.second>b.second;
}
if(!ok1 && !ok2)
{
return a.first<b.first;
}
return (ok1<ok2);
}
int Add(int val, int last)
{
if(last%2==0)
{
return val;
}
return -val;
}
void debug(vector<pair<int,int>> v)
{
for(auto it : v)
{
cerr<<it.first<<' ';
}
}
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<c.size(); i++)
{
for(int j=i+1; j<c.size(); j++)
{
if(!cmp(c[i],c[j]))
{
swap(c[i],c[j]);
}
}
}
int rez = 0;
int last = -1;
for(int i=0; i<c.size(); i++)
{
if(c[i].second==false && c[i].first>2)
{
if(i<c.size()-1)
{
rez+=Add(c[i].first-4,last);
}
else
{
rez+=Add(c[i].first,last);
}
}
else if(c[i].second==true && c[i].first>4)
{
if(i<c.size()-1)
{
rez+=Add(c[i].first-8,last);
}
else
{
rez+=Add(c[i].first,last);
}
}
else
{
rez+=Add(c[i].first,last);
++last;
}
}
cout<<Back(0,0)<<'\n';
// debug(c);
return 0;
}
Compilation message
game.cpp: In function 'int Back(int, bool)':
game.cpp:76:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | if(k==c.size())
| ~^~~~~~~~~~
game.cpp: In function 'int main()':
game.cpp:194:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
194 | for(int i=0; i<c.size(); i++)
| ~^~~~~~~~~
game.cpp:196:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
196 | for(int j=i+1; j<c.size(); j++)
| ~^~~~~~~~~
game.cpp:206:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
206 | for(int i=0; i<c.size(); i++)
| ~^~~~~~~~~
game.cpp:210:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
210 | if(i<c.size()-1)
| ~^~~~~~~~~~~
game.cpp:221:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
221 | if(i<c.size()-1)
| ~^~~~~~~~~~~
game.cpp:151:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
151 | freopen("nr.in","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~
game.cpp:152:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
152 | freopen("nr.out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
