Submission #1297380

#	Time	Username	Problem	Language	Result	Execution time	Memory
1297380		haonk	Cultivation (JOI17_cultivation)	C++20	0 / 100	1 ms	832 KiB

cultivation

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <vector>
#include <array>
#include <deque>
#include <list>
#include <forward_list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <stack>
#include <string>
#include <sstream>
#include <cstring>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <bitset>
#include <tuple>
#include <optional>
#include <variant>
#include <cmath>
#include <cstdlib>
#include <cstdint>
#include <climits>
#include <limits>
#include <random>
#include <chrono>
#include <fstream>
#include <iterator>
#include <regex>
#include <type_traits>
#include <cctype>
#include <cstddef>

#define name "DISPERSAL"
#define ii pair<int,int>
#define se second 
#define fi first 

using namespace std;
using ll = long long;

const int inf = 1e9;

int mx[]={0,1,0,-1},
    my[]={1,0,-1,0};

const int N = 305;

int r,c,n;
ii Q[N];

bool ok(int x,int y){
    return x>0 and x<=r and y>0 and y<=c;
}

namespace sub1{

    bool a[5][5];

    int check[1<<17];

    int backtrack(int mask,int cur,int type=0){
        cout<<type<<'\n';
        cout<<bitset<12>(mask)<<" "<<cur<<'\n';
        for(int i=1;i<=r;++i){
            for(int j=1;j<=c;++j){
                cout<<a[i][j];
            }
            cout<<'\n';
        }
        cout<<'\n';

        if(mask==((1<<c*r)-1)) return cur;
        if(check[mask]!=inf) return check[mask];

        bool tmp[5][5];

        for(int i=1;i<=r;++i){
            for(int j=1;j<=c;++j){
                tmp[i][j] = a[i][j];
            }
        }

        for(int t=0;t<4;++t){
            for(int i=1;i<=r;++i){
                for(int j=1;j<=c;++j){
                    int x = i+mx[t],
                        y = j+my[t];

                    if(!ok(x,y))continue;

                    a[x][y] |= tmp[i][j];
                }
            }
            int premask=mask;
            for(int i=1;i<=r;++i){
                for(int j=1;j<=c;++j){
                    if(a[i][j]==1)premask |= (1<<((i-1)*c+j-1));
                }
            }

            if(mask!=premask) check[mask] = min(check[mask],backtrack(premask,cur+1,t));

            for(int i=1;i<=r;++i){
                for(int j=1;j<=c;++j){
                    a[i][j] = tmp[i][j];
                }
            }
        }

        return check[mask];
    }

    void solve(){
        for(int mask=0; mask<(1<<17); ++mask) check[mask]=inf;

        int mask = 0;
        for(int i=1;i<=n;++i){
            a[Q[i].fi][Q[i].se] = 1;

            mask |= (1<<((Q[i].fi-1)*c+Q[i].se-1));
        }

        cout<<backtrack(mask,0);
    }
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if(fopen(name".inp","r")){
        freopen(name".inp","r",stdin);
        freopen(name".out","w",stdout);
    }
    
    cin>>r>>c>>n;
    for(int i=1;i<=n;++i){
        cin>>Q[i].fi>>Q[i].se;
    }

    sub1::solve();
}

Compilation message (stderr)

cultivation.cpp: In function 'int main()':
cultivation.cpp:139:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  139 |         freopen(name".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
cultivation.cpp:140:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  140 |         freopen(name".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 20
• Subtask 6: 0 / 20