Submission #457741

#	Time	Username	Problem	Language	Result	Execution time	Memory
457741		Tenis0206	Game (eJOI20_game)	C++11	80 / 100	643 ms	40700 KiB

game

#include <bits/stdc++.h>

using namespace std;
const int limit = 150000;
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;
unordered_map<string,int> rez[2];
unordered_map<string,bool> reached[2];
int nrop = 0;
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, string state)
{
    ++nrop;
    reached[turn][state] = true;
    if(turn)
    {
        int Max = -oo;
        for(int i=0; i<c.size(); i++)
        {
            if(state[i]=='1')
            {
                continue;
            }
            int Min = oo;
            string new_state = state;
            new_state[i] = '1';
            if(reached[0][new_state])
            {
                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(reached[1][new_state])
                {
                    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(reached[1][new_state])
                {
                    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(nrop>limit)
            {
                break;
            }
        }
        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[i]=='1')
            {
                continue;
            }
            int Max = -oo;
            string new_state = state;
            new_state[i] = '1';
            if(reached[1][new_state])
            {
                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(reached[0][new_state])
                {
                    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(reached[0][new_state])
                {
                    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(nrop>limit)
            {
                break;
            }
        }
        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';
    }
}
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.second>=4))
    {
        ok1 = true;
    }
    if((b.second==false && b.first>2) || (b.second==true && b.second>=4))
    {
        ok2 = true;
    }
    if(ok1 && ok2)
    {
        return (a.second>b.second);
    }
    if(!ok1 && !ok2)
    {
        return a.first<b.first;
    }
    return (ok1<ok2);
}
signed 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]);
            }
        }
    }
    string init;
    for(int i=0;i<c.size();i++)
    {
        init.push_back('0');
    }
    cout<<Back(1,init)<<'\n';
    return 0;
}

Compilation message (stderr)

game.cpp: In function 'int Back(int, std::string)':
game.cpp:85: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]
   85 |         for(int i=0; i<c.size(); i++)
      |                      ~^~~~~~~~~
game.cpp:140: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]
  140 |         for(int i=0;i<c.size();i++)
      |                     ~^~~~~~~~~
game.cpp: In function 'int main()':
game.cpp:270:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  270 |     for(int i=0;i<c.size();i++)
      |                 ~^~~~~~~~~
game.cpp:272:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  272 |         for(int j=i+1;j<c.size();j++)
      |                       ~^~~~~~~~~
game.cpp:281:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  281 |     for(int i=0;i<c.size();i++)
      |                 ~^~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 0 / 20