oj.uz

Submission #457664

# Submission time Handle Problem Language Result Execution time Memory
457664 2021-08-07T09:28:04 Z Tenis0206 Game (eJOI20_game) C++11
60 / 100
 1 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;
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()
{
    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<<rez<<'\n';
    cout<<Back(0,1)<<'\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:192: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]
  192 |     for(int i=0; i<c.size(); i++)
      |                  ~^~~~~~~~~
game.cpp:194: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]
  194 |         for(int j=i+1; j<c.size(); j++)
      |                        ~^~~~~~~~~
game.cpp:204: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]
  204 |     for(int i=0; i<c.size(); i++)
      |                  ~^~~~~~~~~
game.cpp:208: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]
  208 |             if(i<c.size()-1)
      |                ~^~~~~~~~~~~
game.cpp:219: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]
  219 |             if(i<c.size()-1)
      |                ~^~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 0 ms 204 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 0 ms 332 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 0 ms 332 KB Output is correct
14 Correct 0 ms 332 KB Output is correct
15 Correct 0 ms 332 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 0 ms 332 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 0 ms 332 KB Output is correct
20 Correct 0 ms 204 KB Output is correct
21 Correct 0 ms 332 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 0 ms 204 KB Output is correct
24 Correct 1 ms 332 KB Output is correct
25 Correct 0 ms 204 KB Output is correct
26 Correct 0 ms 332 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Incorrect 0 ms 204 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 0 ms 204 KB Output is correct
23 Correct 1 ms 204 KB Output is correct
24 Correct 0 ms 204 KB Output is correct
25 Correct 0 ms 204 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 1 ms 204 KB Output is correct
29 Correct 1 ms 332 KB Output is correct
30 Correct 0 ms 332 KB Output is correct
31 Correct 1 ms 332 KB Output is correct
32 Correct 1 ms 332 KB Output is correct
33 Correct 0 ms 204 KB Output is correct
34 Correct 0 ms 332 KB Output is correct
35 Correct 0 ms 332 KB Output is correct
36 Correct 1 ms 204 KB Output is correct
37 Correct 0 ms 332 KB Output is correct
38 Correct 0 ms 332 KB Output is correct
39 Correct 0 ms 332 KB Output is correct
40 Correct 0 ms 204 KB Output is correct
41 Correct 0 ms 332 KB Output is correct
42 Correct 0 ms 204 KB Output is correct
43 Correct 0 ms 332 KB Output is correct
44 Correct 0 ms 204 KB Output is correct
45 Correct 0 ms 332 KB Output is correct
46 Correct 1 ms 204 KB Output is correct
47 Correct 0 ms 204 KB Output is correct
48 Correct 1 ms 332 KB Output is correct
49 Correct 0 ms 204 KB Output is correct
50 Correct 0 ms 332 KB Output is correct
51 Correct 0 ms 204 KB Output is correct
52 Correct 0 ms 204 KB Output is correct
53 Correct 0 ms 204 KB Output is correct
54 Correct 0 ms 204 KB Output is correct
55 Correct 0 ms 204 KB Output is correct
56 Correct 0 ms 204 KB Output is correct
57 Correct 1 ms 204 KB Output is correct
58 Correct 0 ms 204 KB Output is correct
59 Incorrect 0 ms 204 KB Output isn't correct
60 Halted 0 ms 0 KB -