QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#487168#5341. Shopping MallsPetroTarnavskyi#TL 0ms0kbC++202.5kb2024-07-22 17:19:462024-07-22 17:19:46

Judging History

你现在查看的是最新测评结果

  • [2024-07-22 17:19:46]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2024-07-22 17:19:46]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

const int mod1 = 1e9 + 7;
const int mod2 = 1e9 + 9;
const LL mod = (LL)mod1 * mod2;
const int P = 474747;
const string sep = ".,:;?!";

LL add(LL a, LL b)
{
	return a + b < mod ? a + b : a + b - mod;
}

LL mult(LL a, LL b)
{
	return (__int128)a * b % mod;
}

LL h(string s)
{
	LL res = 0;
	LL pw = 1;
	for (char c : s)
	{
		res = add(res, mult(tolower(c), pw));
		pw = mult(pw, P);
	}
	return res;
}

int n;

void solve()
{
	set<LL> words, subsequences;
	words.insert(h("Joe"));
	auto memorize = [&](const vector<string>& sentence, bool needPrint)
	{
		for (const string& word : sentence)
		{
			LL curH = h(word);
			if (!words.count(curH))
			{
				words.insert(curH);
				if (needPrint)
				{
					cout << "What does the word \"" << word << "\" mean?\n";
				}
			}
		}		
		bool needAskSentence = false;
		FOR(i, 0, SZ(sentence))
		{
			string seq = sentence[i];
			FOR(j, 1, n)
			{
				if (i + j >= SZ(sentence))
					break;
				seq += " " + sentence[i + j];
				LL curH = h(seq);
				if (!subsequences.count(curH))
				{
					subsequences.insert(curH);
					needAskSentence = true;
				}
			}
		}
		if (needAskSentence && needPrint)
		{
			cout << "What does the sentence \"";
			FOR(i, 0, SZ(sentence))
			{
				if (i > 0)
					cout << " ";
				cout << sentence[i];
			}
			cout << "\" mean?\n";
		}
	};
	
	vector<string> sentence;
	bool needPrint = false;
	while (true)
	{
		string word;
		cin >> word;
		if (SZ(word) == 1 && find(ALL(sep), word[0]) != sep.end())
		{
			memorize(sentence, needPrint);
			sentence.clear();
		}
		else if (word == "*")
		{
			memorize(sentence, needPrint);
			sentence.clear();
			needPrint = true;
		}
		else if (word == "#")
		{
			memorize(sentence, needPrint);
			sentence.clear();
			break;
		}
		else
		{
			sentence.PB(word);
		}
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	assert(tolower(' ') == ' ');
	assert(tolower('a') == 'a');
	assert(tolower('A') == 'a');
	int tc = 0;
	while (cin >> n)
	{
		tc++;
		if (tc > 1)
			cout << "\n";
		cout << "Learning case " << tc << "\n";
		solve();
	}
	return 0;
}

 

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Time Limit Exceeded

input:

6 7
3 2 3
3 5 3
2 2 3
2 6 4
1 1 3
1 4 2
0 1 walking
0 2 lift
1 2 stairs
2 3 walking
3 4 escalator
5 3 escalator
4 5 walking
5
0 1
1 2
3 5
5 3
5 1

output:


result: