oj.uz

Submission #18756

# Submission time Handle Problem Language Result Execution time Memory
18756 2016-02-15T04:36:58 Z joonas 백신 (KOI13_vaccine) C++
24 / 24
 525 ms 3708 KB 
#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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1732 KB Output is correct
2 Correct 0 ms 1732 KB Output is correct
3 Correct 0 ms 1732 KB Output is correct
4 Correct 0 ms 1732 KB Output is correct
5 Correct 0 ms 1732 KB Output is correct
6 Correct 0 ms 1732 KB Output is correct
7 Correct 0 ms 1732 KB Output is correct
8 Correct 0 ms 1732 KB Output is correct
9 Correct 0 ms 1732 KB Output is correct
10 Correct 0 ms 1732 KB Output is correct

Subtask #2
3.12 / 3.12

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1732 KB Output is correct
2 Correct 0 ms 1732 KB Output is correct
3 Correct 0 ms 1732 KB Output is correct
4 Correct 0 ms 1732 KB Output is correct
5 Correct 0 ms 1732 KB Output is correct
6 Correct 0 ms 1732 KB Output is correct
7 Correct 0 ms 1732 KB Output is correct
8 Correct 0 ms 1732 KB Output is correct
9 Correct 0 ms 1732 KB Output is correct
10 Correct 0 ms 1732 KB Output is correct

Subtask #3
3.6 / 3.6

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1732 KB Output is correct
2 Correct 0 ms 1732 KB Output is correct
3 Correct 1 ms 1732 KB Output is correct
4 Correct 3 ms 1732 KB Output is correct
5 Correct 0 ms 1732 KB Output is correct
6 Correct 0 ms 1732 KB Output is correct
7 Correct 0 ms 1732 KB Output is correct
8 Correct 0 ms 1732 KB Output is correct
9 Correct 8 ms 1732 KB Output is correct
10 Correct 0 ms 1732 KB Output is correct

Subtask #4
4.32 / 4.32

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1732 KB Output is correct
2 Correct 3 ms 1732 KB Output is correct
3 Correct 0 ms 1732 KB Output is correct
4 Correct 0 ms 1732 KB Output is correct
5 Correct 0 ms 1732 KB Output is correct
6 Correct 0 ms 1732 KB Output is correct
7 Correct 2 ms 1732 KB Output is correct
8 Correct 9 ms 1732 KB Output is correct
9 Correct 2 ms 1732 KB Output is correct
10 Correct 0 ms 1732 KB Output is correct

Subtask #5
4.8 / 4.8

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1732 KB Output is correct
2 Correct 23 ms 1864 KB Output is correct
3 Correct 24 ms 1732 KB Output is correct
4 Correct 151 ms 3576 KB Output is correct
5 Correct 7 ms 1732 KB Output is correct
6 Correct 8 ms 1732 KB Output is correct
7 Correct 11 ms 1732 KB Output is correct
8 Correct 392 ms 1732 KB Output is correct
9 Correct 496 ms 1732 KB Output is correct
10 Correct 21 ms 1732 KB Output is correct

Subtask #6
5.52 / 5.52

# Verdict Execution time Memory Grader output
1 Correct 37 ms 1864 KB Output is correct
2 Correct 172 ms 2656 KB Output is correct
3 Correct 242 ms 3184 KB Output is correct
4 Correct 17 ms 1732 KB Output is correct
5 Correct 26 ms 1732 KB Output is correct
6 Correct 35 ms 1732 KB Output is correct
7 Correct 150 ms 3708 KB Output is correct
8 Correct 525 ms 1732 KB Output is correct
9 Correct 28 ms 1732 KB Output is correct
10 Correct 33 ms 1732 KB Output is correct