QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#487168 | #5341. Shopping Malls | PetroTarnavskyi# | TL | 0ms | 0kb | C++20 | 2.5kb | 2024-07-22 17:19:46 | 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