QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#466563#7686. The Phantom MenaceH__MRE 733ms353320kbC++143.1kb2024-07-07 22:19:582024-07-07 22:19:58

Judging History

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

  • [2024-10-08 14:11:03]
  • hack成功,自动添加数据
  • (/hack/941)
  • [2024-10-08 10:05:28]
  • hack成功,自动添加数据
  • (/hack/940)
  • [2024-10-07 19:51:15]
  • hack成功,自动添加数据
  • (/hack/938)
  • [2024-10-07 19:28:01]
  • hack成功,自动添加数据
  • (/hack/937)
  • [2024-10-07 17:16:32]
  • hack成功,自动添加数据
  • (/hack/936)
  • [2024-10-07 16:53:09]
  • hack成功,自动添加数据
  • (/hack/935)
  • [2024-10-07 16:22:17]
  • hack成功,自动添加数据
  • (/hack/934)
  • [2024-07-07 22:19:58]
  • 评测
  • 测评结果:RE
  • 用时:733ms
  • 内存:353320kb
  • [2024-07-07 22:19:58]
  • 提交

answer

#include<vector>
#include<stack>
#include<iostream>
#include<map>

using namespace std;
#define endl "\n"
#define ll long long
const int N = 4e6 + 10;
int n, m;

vector<int > ed[N];
stack<int > st;

vector<int > ansa;
vector<int > ansb;
int in[N];
int out[N];
int cnt;
map<pair<int, int>, vector<int > > mpa;
map<pair<int, int>, vector<int > > mpb;
string sa[N];
string sb[N];
map<string, int> mp;
map<int, string> fmp;
int mode;
bool sta[N];
void dfs(int u)
{
	sta[u] = 1;
	while (!ed[u].empty())
	{
		int tmp = ed[u].back();
		ed[u].pop_back();
		dfs(tmp);
	}
	if (st.size() != 0) {
		if (st.size() & 1)
		{
			if (mpb[{u, st.top()}].size() == 0)
				mode = 1;
		}
		else {
				if (mpa[{u, st.top()}].size() == 0) 
					mode = 1;
			}
	}
	st.push(u);
}
void solve()
{

	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> sa[i];
	for (int i = 1; i <= n; i++)
		cin >> sb[i];
	for (int i = 0; i < m; i++)
	{
		mp.clear();
		fmp.clear();
		for (int j = 1; j <= cnt; j++) ed[j].clear(), in[j] = out[j] = 0;
		mpa.clear();
		mpb.clear();
		ansa.clear();
		ansb.clear();
		cnt = 1;
		for (int j = 1; j <= n; j++)
		{
			string tmpa = sa[j].substr(0, i), tmpb = sa[j].substr(i);
			if (mp[tmpa] == 0) mp[tmpa] = cnt++, fmp[cnt - 1] = tmpa;
			if (mp[tmpb] == 0) mp[tmpb] = cnt++, fmp[cnt - 1] = tmpb;
			out[mp[tmpa]]++;
			in[mp[tmpb]]++;
			mpa[{mp[tmpa], mp[tmpb]}].push_back(j);
			ed[mp[tmpa]].push_back(mp[tmpb]);
		}
		for (int j = 1; j <= n; j++)
		{
			string tmpa = sb[j].substr(0, m - i), tmpb;
			if (i != 0) tmpb = sb[j].substr(m - i, i);
			else tmpb = "";
			if (mp[tmpa] == 0) mp[tmpa] = cnt++, fmp[cnt - 1] = tmpa;
			if (mp[tmpb] == 0) mp[tmpb] = cnt++, fmp[cnt - 1] = tmpb;
			out[mp[tmpa]]++;
			in[mp[tmpb]]++;
			mpb[{mp[tmpa], mp[tmpb]}].push_back(j);
			ed[mp[tmpa]].push_back(mp[tmpb]);
		}
		bool flag = 0;
		for (int j = 1; j < cnt; j++)
			if (in[j] != out[j]) {
				flag = 1; break;
			}
		if (flag) continue;
		for (int i = 0; i <= cnt; i++) sta[i] = 0;
		for (int i = 1; i < cnt; i++) {
			if (sta[i]) continue;
			mode = 0;
			dfs(i);
			int pre = st.top();
			st.pop();
			int cc = 0;
			while (!st.empty()) {
				int now = st.top();
				st.pop();
				if (mode == 0)
				{
					if (cc & 1) {
						ansb.push_back(mpb[{pre, now}].back());
						mpb[{pre, now}].pop_back();
					}
					else {
						ansa.push_back(mpa[{pre, now}].back());
						mpa[{pre, now}].pop_back();
					}
					
				}
				else
				{
					if (cc & 1) {
						ansa.push_back(mpa[{pre, now}].back());
						mpa[{pre, now}].pop_back();
					}
					else {
						ansb.push_back(mpb[{pre, now}].back());
						mpb[{pre, now}].pop_back();
					}
				}
				pre = now;
				cc++;
			}
		}

		if (ansa.size() != n || ansb.size() != n) return cout << -1 << endl, void();
		for (int j : ansa) cout << j << " ";
		cout << endl;
		for (int j : ansb) cout << j << " ";
		cout << endl;
		return;
	}

	cout << -1 << endl;

}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t--)
		solve();
}

詳細信息

Test #1:

score: 100
Accepted
time: 40ms
memory: 353268kb

input:

2
3 3
abc
ghi
def
bcd
efg
hia
1 3
abc
def

output:

1 3 2 
1 2 3 
-1

result:

ok 2 cases (2 test cases)

Test #2:

score: 0
Accepted
time: 733ms
memory: 353320kb

input:

1000000
1 1
b
b
1 1
a
b
1 1
b
a
1 1
a
a
1 1
b
b
1 1
a
b
1 1
b
a
1 1
a
a
1 1
b
b
1 1
a
b
1 1
b
a
1 1
a
a
1 1
b
b
1 1
a
b
1 1
b
a
1 1
a
a
1 1
b
b
1 1
a
b
1 1
b
a
1 1
a
a
1 1
b
b
1 1
a
b
1 1
b
a
1 1
a
a
1 1
b
b
1 1
a
b
1 1
b
a
1 1
a
a
1 1
b
b
1 1
a
b
1 1
b
a
1 1
a
a
1 1
b
b
1 1
a
b
1 1
b
a
1 1
a
a
1 1
...

output:

1 
1 
-1
-1
1 
1 
1 
1 
-1
-1
1 
1 
1 
1 
-1
-1
1 
1 
1 
1 
-1
-1
1 
1 
1 
1 
-1
-1
1 
1 
1 
1 
-1
-1
1 
1 
1 
1 
-1
-1
1 
1 
1 
1 
-1
-1
1 
1 
1 
1 
-1
-1
1 
1 
1 
1 
-1
-1
1 
1 
1 
1 
-1
-1
1 
1 
1 
1 
-1
-1
1 
1 
1 
1 
-1
-1
1 
1 
1 
1 
-1
-1
1 
1 
1 
1 
-1
-1
1 
1 
1 
1 
-1
-1
1 
1 
1 
1 
-1
-1
...

result:

ok 1000000 cases (1000000 test cases)

Test #3:

score: -100
Runtime Error

input:

500000
1 2
dd
ba
1 2
cd
ba
1 2
bd
ba
1 2
ad
ba
1 2
dc
ba
1 2
cc
ba
1 2
bc
ba
1 2
ac
ba
1 2
db
ba
1 2
cb
ba
1 2
bb
ba
1 2
ab
ba
1 2
da
ba
1 2
ca
ba
1 2
ba
ba
1 2
aa
ba
1 2
dd
aa
1 2
cd
aa
1 2
bd
aa
1 2
ad
aa
1 2
dc
aa
1 2
cc
aa
1 2
bc
aa
1 2
ac
aa
1 2
db
aa
1 2
cb
aa
1 2
bb
aa
1 2
ab
aa
1 2
da
aa
1 2...

output:


result: