Submission #412198

#	Time	Username	Problem	Language	Result	Execution time	Memory
412198		Theo830	Game (eJOI20_game)	C++17	20 / 100	313 ms	11892 KiB

game

#include <bits/stdc++.h>
using namespace std;
typedef int ll;
ll INF = 1e9+7;
ll MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ii,ll>
#define f(i,a,b) for(ll i = a;i < b;i++)
#define pb push_back
#define vll vector<ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
///I hope I will get uprating and don't make mistakes
///I will never stop programming
///sqrt(-1) Love C++
///Please don't hack me
///@TheofanisOrfanou Theo830
///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst)
///Stay Calm
///Look for special cases
///Beware of overflow and array bounds
///Think the problem backwards
///Training
ll n,m;
vll comp;
vector<ll>ch;
bool v[20][20];
char arr[21][20],ar[20][21];
bool in(ll x,ll y){
    return (x < n && y < m) && min(x,y) >= 0;
}
typedef pair<set<ii>,ll> mr;
ll posa = 0,g = 1;
void dfs(ll x,ll y){
    v[x][y] = 1;
    posa++;
    if(arr[x+1][y] == '0' && !in(x+1,y)){
        g = 0;
    }
    else if(arr[x][y] == '0' && !in(x-1,y)){
        g = 0;
    }
    else if(!in(x,y+1) && ar[x][y+1] == '0'){
        g = 0;
    }
    else if(!in(x,y-1) && ar[x][y] == '0'){
        g = 0;
    }
    if((in(x+1,y) && !v[x+1][y]) && arr[x+1][y] == '0'){
        dfs(x+1,y);
    }
    if((in(x-1,y) && !v[x-1][y]) && arr[x][y] == '0'){
        dfs(x-1,y);
    }
    if((in(x,y+1) && !v[x][y+1]) && ar[x][y+1] == '0'){
        dfs(x,y+1);
    }
    if((in(x,y-1) && !v[x][y-1]) && ar[x][y] == '0'){
        dfs(x,y-1);
    }
}
map<mr,ll>mp;
map<mr,bool>ok;
ll diff = 0;
ll solve(ll p,set<ii>s){
    if(s.empty()){
        return 0;
    }
    if(ok[mr(s,p)]){
        return mp[mr(s,p)];
    }
    ll ans;
    if(p == 0){
        ans = -INF;
        set<ii>s2 = s;
        for(auto f:s2){
            ii x;
            x.F = f.F;
            x.S = f.S;
            if(x.S == 2){
                s.erase(x);
                ans = max(ans,solve(p,s) + ch[x.F] + 1);
                s.insert(x);
            }
            else if(x.S == 1){
                s.erase(x);
                x.S = 2;
                s.insert(x);
                ans = max(ans,solve(p,s) + comp[x.F] - (ch[x.F]+1));
                s.erase(x);
                x.S = 1;
                s.insert(x);
            }
            else{
                s.erase(x);
                x.S = 1;
                s.insert(x);
                ans = max(ans,solve(p^1,s));
                s.erase(x);
                x.S = 0;
                s.insert(x);
            }
        }
    }
    else{
        ans = INF;
        set<ii>s2 = s;
        for(auto f:s2){
            ii x;
            x.F = f.F;
            x.S = f.S;
            if(x.S == 2){
                s.erase(x);
                ans = min(ans,solve(p,s) - ch[x.F] - 1);
                s.insert(x);
            }
            else if(x.S == 1){
                s.erase(x);
                x.S = 2;
                s.insert(x);
                ans = min(ans,solve(p,s) - comp[x.F] + ch[x.F] + 1);
                s.erase(x);
                x.S = 1;
                s.insert(x);
            }
            else{
                s.erase(x);
                x.S = 1;
                s.insert(x);
                ans = min(ans,solve(p^1,s));
                s.erase(x);
                x.S = 0;
                s.insert(x);
            }
        }
    }
    ok[mr(s,p)] = 1;
    mp[mr(s,p)] = ans;
    return ans;
}
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    f(i,0,n+1){
        f(j,0,m){
            cin>>arr[i][j];
        }
    }
    f(i,0,n){
        f(j,0,m+1){
            cin>>ar[i][j];
        }
    }
    ll ans = -INF;
    memset(v,0,sizeof v);
    f(i,0,n){
        f(j,0,m){
            if(!v[i][j]){
                posa = 0;
                g = 1;
                dfs(i,j);
                if(posa != 1 || (arr[i][j] == '0' || arr[i+1][j] == '0' || ar[i][j] == '0' || ar[i][j+1] == '0')){
                    comp.pb(posa);
                    ch.pb(g);
                }
            }
        }
    }
    set<ii>e;
    ll pos = 0;
    for(auto x:comp){
        e.insert(ii(pos,0LL));
        assert(ch[pos]+1 <= comp[pos]);
        pos++;
    }
    cout<<solve(0,e);
}
/*
3 3
000
111
011
110
1010
1000
1001

5 5
00100
10100
11010
00100
01000
11100
011111
001011
101011
110111
100111
*/

Compilation message (stderr)

game.cpp: In function 'int main()':
game.cpp:174:14: warning: unused variable 'x' [-Wunused-variable]
  174 |     for(auto x:comp){
      |              ^
game.cpp:157:8: warning: unused variable 'ans' [-Wunused-variable]
  157 |     ll ans = -INF;
      |        ^~~

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