QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#243061#7331. The Catcher in the RyePetroTarnavskyi#WA 4ms58316kbC++172.4kb2023-11-07 20:30:352023-11-07 20:30:35

Judging History

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

  • [2023-11-07 20:30:35]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:58316kb
  • [2023-11-07 20:30:35]
  • 提交

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