Submission #18756

#	Time	Username	Problem	Language	Result	Execution time	Memory
18756		joonas	백신 (KOI13_vaccine)	C++98	24 / 24	525 ms	3708 KiB

vaccine

#include <iostream>
#include <algorithm>  //reverse
#include <vector>
#include <string>
#include <map>
using namespace std;

#define varr vector<int>

map< varr, bool > cache;

vector< varr > RabinKarp(varr s, varr p, int len)
{
	int si, slen = s.size(), plen = p.size();
	if (slen < plen)
		swap(s, p), swap(slen, plen);

	vector< varr > result;
	for (int grb = 0; grb <= plen - len; ++grb)
	{
		int Hsum = 0, tsum = 0;
		for (int i = 0; i < len && i < slen; ++i){
			tsum += s[i];
		}
		for (int i = grb; i < grb + len && i < plen; ++i){
			Hsum += p[i];
		}

		// save에 일치한 시작 위치를 저장
		int save[1001] = { 0, }, size = 0;
		for (si = 0; si < slen - len; ++si)
		{
			if (Hsum == tsum) save[size++] = si;
			tsum = tsum - s[si] + s[si + len];
		}
		if (Hsum == tsum) save[size++] = si;

		for (int i = 0; i < size; ++i)
		{
//          cout<< save[i] <<" : ";

			// 병렬적으로 확인하여 모두 일치하면 통과
			int flag = 0;
			for (int k1 = save[i], k2 = grb; k1 < save[i] + len; ++k1, ++k2)
			{
				if (s[k1] != p[k2]){ flag = 1; break; }
			}
			// 아니라면 다음 save 확인
			if (flag) continue;

			// 검사에 통과한 '시작 위치'~'시작 위치+길이' 만 저장
			varr tempV;
			for (int k = save[i]; k < save[i] + len; ++k)
			{
//              cout<< s[k] <<' ';
				tempV.push_back(s[k]);
			}
//          cout<<endl;

			// 검사에 통과한 벡터를 그룹에 추가
			if (!cache[tempV]){
				result.push_back(tempV);
				cache[tempV] = true;
			}
		}
	}
	return result;
}

int main()
{
	int nT, K;
	varr _s, p;
	vector< varr > s;

	int m, temp;
	cin >> nT >> K;

	cin >> m;
	s.push_back(_s);
	while (m--){
		cin >> temp;
		s[0].push_back(temp);
	}

	while (--nT > 0)
	{
		cin >> m;
		while (m--){
			cin >> temp;
			p.push_back(temp);
		}

		vector< varr > v, rv, r;
		for (int inS = 0; inS < s.size(); ++inS)
		{
			varr tempS = s[inS];
			v = RabinKarp(tempS, p, K);
			reverse(tempS.begin(), tempS.end());
			rv = RabinKarp(tempS, p, K);
			v.insert(v.end(), rv.begin(), rv.end());
			r.insert(r.end(), v.begin(), v.end());
		}

		s = r;
		p.clear(), cache.clear();
	}

	if (s.size() > 0) cout << "YES";
	else cout << "NO";

	return 0;
}

• Subtask 1: 2.64 / 2.64
• Subtask 2: 3.12 / 3.12
• Subtask 3: 3.6 / 3.6
• Subtask 4: 4.32 / 4.32
• Subtask 5: 4.8 / 4.8
• Subtask 6: 5.52 / 5.52