Submission #261408

#	Time	Username	Problem	Language	Result	Execution time	Memory
261408		limabeans	Virus Experiment (JOI19_virus)	C++17	0 / 100	2082 ms	94468 KiB

virus

#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;

const ll mod = 1e9+7;
const int maxn = 801;
const int inf = 2e9;


int m,r,c;
string s;
vector<vector<int>> g;
const string dir = "NSEW";
int ls[25];

map<char,int> X;

int sim(int x, int y) {
    int n = g.size();
    int m = g[0].size();

    
    map<int,set<int>> mp; // mask->coords
    map<int,int> state; //coord->mask
    
    for (int i=0; i<n; i++) {
	for (int j=0; j<m; j++) {
	    mp[0].insert(i*m+j);
	    state[i*m+j]=0;
	}
    }

    auto get = [&](int i, int j) {
	return i*m+j;
    };

    int infected = 0;

    // i,j is infected, edit the neighbor states
    auto add = [&](int i, int j) {
	infected++;
	int msk=-1, msk2=-1;
	if (i-1>=0) {
	    int nei = get(i-1,j);
	    if (state.count(nei)) {
		msk=state[nei];
		msk2 = msk | (1<<X['S']);
		mp[msk].erase(nei);
		state[nei]=msk2;
		mp[msk2].insert(nei);
	    }
	}
	if (i+1<n) {
	    int nei = get(i+1,j);
	    if (state.count(nei)) {
		msk=state[nei];
		msk2 = msk | (1<<X['N']);
		mp[msk].erase(nei);
		state[nei]=msk2;
		mp[msk2].insert(nei);
	    }
	}
	if (j+1<m) {
	    int nei = get(i,j+1);
	    if (state.count(nei)) {
		msk=state[nei];
		msk2 = msk | (1<<X['W']);
		mp[msk].erase(nei);
		state[nei]=msk2;
		mp[msk2].insert(nei);
	    }
	}
	if (j-1>=0) {
	    int nei = get(i,j-1);
	    if (state.count(nei)) {
		msk=state[nei];
		msk2 = msk |(1<<X['E']);
		mp[msk].erase(nei);
		state[nei]=msk2;
		mp[msk2].insert(nei);
	    }
	}
    };
    mp[0].erase(x*m+y);
    state.erase(x*m+y);
    add(x,y);

    // for (auto p: state) {
    // 	cout<<p.first<<": "<<bitset<4>(p.second)<<endl;
    // }

    while (true) {
	bool ed = false;
	for (auto p: mp) {
	    int mask = p.first;
	    vector<int> v;
	    for (int dat: p.second) {
		int r=dat/m;
		int c=dat%m;
		if (g[r][c] > 0 && ls[mask] >= g[r][c]) {
		    v.push_back(dat);			
		}
	    }
	    if (v.size()) {
		for (int dat: v) {
		    mp[mask].erase(dat);
		    state.erase(dat);
		    add(dat/m,dat%m);
		}
		ed = true;
		break;
	    }
	}
	if (!ed) break;
    }


    return infected;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);
    for (int i=0; i<4; i++) X[dir[i]]=i;

    cin>>m>>r>>c;
    g = vector<vector<int>>(r, vector<int>(c));
    cin>>s;
    for (int i=0; i<r; i++) {
	for (int j=0; j<c; j++) {
	    cin>>g[i][j];
	}
    }

    s += s;

    for (int mask=1; mask<16; mask++) {
	int len = s.length();
	set<char> st;
	for (int j=0; j<4; j++) {
	    if (mask>>j&1) st.insert(dir[j]);
	}
	bool all = true;
	for (int i=0; i<len; i++) {
	    if (!st.count(s[i])) {
		all=false;
		break;
	    }
	}
	if (all) {
	    ls[mask]=inf;
	    continue;
	}

	int best = 0;
	for (int i=0; i<len; ) {
	    if (!st.count(s[i])) {
		i++;
		continue;
	    }
	    int j=i;
	    while (j<len && st.count(s[j])) {
		j++;
	    }
	    best = max(best, j-i);
	    i=j;
	}

	ls[mask] = best;
    }


    map<int,int> mp;

    for (int i=0; i<r; i++) {
	for (int j=0; j<c; j++) {
	    if (g[i][j] > 0) {
		int cur = sim(i,j);
		//cout<<i+1<<","<<j+1<<": "<<cur<<endl;
		mp[cur]++;
	    }
	}
    }

    cout<<mp.begin()->first<<endl;
    cout<<mp.begin()->second<<endl;
    
    
    return 0;
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 6
• Subtask 3: 0 / 80