QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#243061 | #7331. The Catcher in the Rye | PetroTarnavskyi# | WA | 4ms | 58316kb | C++17 | 2.4kb | 2023-11-07 20:30:35 | 2023-11-07 20:30:35 |
Judging History
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 = 1'000'000'007;
const int mod2 = 1'000'000'009;
const LL mod = (LL)mod1 * mod2;
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;
}
const int N = 1'000'047;
const int p = 47;
LL pw[N];
vector<PII> g[N];
VI was[N];
map<LL, int> m[2];
int sz = 0;
int insert(int t, LL x)
{
if (m[t].count(x))
return m[t][x];
return m[t][x] = sz++;
}
void clear()
{
FOR (i, 0, sz)
{
g[i].clear();
was[i].clear();
}
m[0].clear();
m[1].clear();
sz = 0;
}
void solve()
{
int n;
cin >> n;
vector<string> s(n);
FOR (i, 0, n)
{
cin >> s[i];
vector<LL> hs(SZ(s[i]) + 1);
hs[0] = 0;
FOR (j, 0, SZ(s[i]))
hs[j + 1] = add(hs[j], mult(pw[j], s[i][j] - 'a' + 1));
LL hash = 0;
RFOR (j, SZ(s[i]), 0)
{
hash = mult(hash, p);
hash = add(hash, s[i][j] - 'a' + 1);
int u = insert(0, hs[j]);
int v = insert(1, hash);
g[u].PB({v, i});
g[v].PB({u, i});
cerr << i << ' ' << v << ' ' << u << '\n';
}
}
VI idx(sz);
cerr << SZ(idx) << '\n';
iota(ALL(idx), 0);
sort(ALL(idx), [&](int i, int j)
{
return SZ(g[i]) > SZ(g[j]);
});
for (auto v : idx)
{
for (auto [to, id] : g[v])
{
FOR (i, 0, SZ(g[to]))
{
int u = g[to][i].F;
int j = g[to][i].S;
if (u == v)
{
swap(g[to][i], g[to][SZ(g[to]) - 1]);
continue;
}
was[u].PB(id);
was[u].PB(j);
if (SZ(was[u]) == 4)
{
cout << "YES\n";
cout << s[was[u][0]] << ' ' << s[was[u][1]] << '\n';
cout << s[was[u][2]] << ' ' << s[was[u][3]] << '\n';
clear();
return;
}
}
g[to].pop_back();
}
for (auto [to, id] : g[v])
{
for (auto [u, j] : g[to])
was[u].clear();
}
}
cout << "NO\n";
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout << fixed << setprecision(15);
pw[0] = 1;
FOR (i, 1, N) pw[i] = mult(pw[i - 1], p);
int t;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 4ms
memory: 58316kb
input:
2 10 3 4 3 1 1 1 21 5 12 4 4 3 4
output:
YES 1 21 1 21 NO
result:
wrong output format Expected double, but "YES" found