QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#246317#2830. Data Structurenameless_story#WA 1ms3516kbC++206.0kb2023-11-10 18:59:292023-11-10 18:59:30

Judging History

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

  • [2023-11-10 18:59:30]
  • 评测
  • 测评结果：WA
  • 用时：1ms
  • 内存：3516kb
查看
  • [2023-11-10 18:59:29]
  • 提交

answer

#include"bits/stdc++.h"
using namespace std;
typedef long long ll;
template<class T1,class T2> bool cmin(T1 &x,const T2 &y) { if (y<x) { x=y; return 1; }return 0; }
template<class T1,class T2> bool cmax(T1 &x,const T2 &y) { if (x<y) { x=y; return 1; }return 0; }
#define all(x) (x).begin(),(x).end()
mt19937 rnd(3456);
int main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	int n,m,i,j;
	n=5; m=7;
	while (cin>>n>>m)
	// int T=1000;
	// while (T--)
	{
		vector<vector<int>> a(m);
		vector<int> pos(n);
		vector<int> empty;
		// for (i=0; i<n; i++)
		// {
		// 	int x;
		// 	x=rnd()%m;
		// 	while (a[x].size()==2) x=rnd()%m;
		// 	a[x].push_back(i); pos[i]+=x;
		// 	x=rnd()%m;
		// 	while (a[x].size()==2) x=rnd()%m;
		// 	a[x].push_back(i); pos[i]+=x;
		// }
		// for (i=0; i<m; i++) if (a[i].size()==0) empty.push_back(i);
		for (i=0; i<m; i++)
		{
			int sz;
			cin>>sz;
			a[i].resize(sz);
			for (int &x:a[i])
			{
				cin>>x;
				pos[--x]+=i;
			}
			if (sz==0) empty.push_back(i);
		}
		// cerr<<"__\n";
		// for (int i=0; i<m; i++)
		// {
		// 	for (int x:a[i]) cerr<<x<<' '; cerr<<endl;
		// }
		auto b=a;
		auto solve=[&]() -> vector<pair<int,int>>
			{
				vector<pair<int,int>> ans;
				/*auto onesingle=[&](int i)
					{
						// cerr<<"onesingle "<<i<<endl;
						assert(a[i].size()==1);
						int x=a[i][0];
						int j=pos[x]-i;
						assert(a[j].size());
						if (a[j].back()==x)
						{
							ans.push_back({j,i});
							a[i]={x,x};
							a[j].pop_back();
							pos[x]=i*2;
							if (!a[j].size()) empty.push_back(j);
							return;
						}
						assert(a[j].size()==2);
						assert(a[j][0]==x);
						assert(empty.size());
						int v=empty.back(); empty.pop_back();
						ans.push_back({j,v});
						ans.push_back({j,i});
						empty.push_back(j);
						a[v]={a[j][1]};
						pos[a[v][0]]+=v-j;
						a[j]={ };
						a[i]={x,x};
						pos[x]=i*2;
						return;
					};*/
				function<void(int)> one=[&](int i)
					{
						// cerr<<"one "<<i<<endl;
						assert(a[i].size()==1);
						int x=a[i][0];
						int j=pos[x]-i;
						assert(a[j].size());
						if (a[j].back()==x)
						{
							ans.push_back({j,i});
							a[i]={x,x};
							a[j].pop_back();
							pos[x]=i*2;
							if (!a[j].size()) empty.push_back(j);
							if (a[j].size()==1) one(j);
							return;
						}
						assert(a[j].size()==2);
						assert(a[j][0]==x);
						// assert(empty.size());
						if (empty.size()==0) return;
						int v=empty.back(); empty.pop_back();
						ans.push_back({j,v});
						ans.push_back({j,i});
						empty.push_back(j);
						a[v]={a[j][1]};
						pos[a[v][0]]+=v-j;
						a[j]={ };
						a[i]={x,x};
						pos[x]=i*2;
						one(v);
						return;
					};
				auto twoup=[&](int i)
					{
						// cerr<<"twoup "<<i<<endl;
						assert(a[i].size()==2&&pos[a[i][0]]==pos[a[i][1]]);
						int x=a[i][1],y=a[i][0];
						int j=pos[x]-i;
						assert(empty.size());
						int v=empty.back(); empty.pop_back();
						if (a[j][0]!=y)
						{
							assert((a[j]==vector{x,y}));
							ans.push_back({j,v});
							ans.push_back({i,j});
							ans.push_back({i,v});
							pos[x]=j*2;
							pos[y]=v*2;
							a[i]={ };
							a[j]={x,x};
							a[v]={y,y};
							return;
						}
						assert((a[j]==vector{y,x}));
						ans.push_back({j,v});
						ans.push_back({i,v});
						ans.push_back({j,i});
						pos[x]=v*2;
						pos[y]=i*2;
						a[i]={y,y};
						a[v]={x,x};
						a[j]={ };
						empty.push_back(j);
					};
				auto two=[&](int i)
					{
						// cerr<<"two "<<i<<endl;
						int x=a[i][1];
						int j=pos[x]-i;
						assert(a[j].size()==2);
						int e1=empty.back(); empty.pop_back();
						ans.push_back({j,e1});
						if (a[j][1]==x)
						{
							ans.push_back({i,e1});
							a[e1]={x,x};
							pos[x]=e1*2;
							a[i].pop_back(); a[j].pop_back();
							one(i);
							assert(a[j].size()==0);
							return;
						}
						pos[a[j].back()]+=e1-j;
						a[e1]={a[j].back()};
						ans.push_back({i,j});
						a[j]={x,x};
						pos[x]=j*2;
						a[i].pop_back();
						one(i);
						assert(a[e1].size()==0);
					};
				// for (i=0; i<m&&empty.size()>=2; i++) if (a[i].size()==2&&a[i][0]!=a[i][1]) two(i);
				for (i=0; i<m; i++) if (a[i].size()==1)
				{
					int x=a[i][0];
					if (a[pos[x]-i]==vector{x}) one(i);
				}
				for (i=0; i<m; i++) if (a[i].size()==1)
				{
					int x=a[i][0];
					if (a[pos[x]-i].back()==x) one(i);
				}
				for (i=0; i<m&&empty.size(); i++) if (a[i].size()==1)
				{
					int x=pos[a[i][0]]-i;
					int D=a[x][1];
					int y=pos[D]-x;
					if (a[y].back()==D) one(i);
				}
				for (i=0; i<m&&empty.size(); i++) if (a[i].size()==1)
				{
					one(i);
				}
				if (empty.size()) for (i=0; i<m; i++) assert(a[i].size()!=1);
				for (i=0; i<m&&empty.size(); i++) if (a[i].size()==2&&a[i][0]!=a[i][1]&&pos[a[i][0]]==pos[a[i][1]]) twoup(i);
				if (empty.size()) for (i=0; i<m; i++) assert(a[i].size()!=1);
				for (i=0; i<m&&empty.size()>=2; i++) if (a[i].size()==2&&a[i][0]!=a[i][1]) two(i);
				if (empty.size()) for (i=0; i<m; i++) assert(a[i].size()!=1);
				for (i=0; i<m; i++) if (a[i].size())
				{
					if (a[i].size()!=2)
					{
						assert(empty.size()<2);
						return {{-1,-1}};
					}
					if (a[i][0]!=a[i][1])
					{
						assert(empty.size()<2);
						return {{-1,-1}};
					}
				}
				return ans;
			};
		auto ans=solve();
		if (ans==vector{pair{-1,-1}}) cout<<"-1\n";
		else
		{
			// if (ans.size()>3*n/2)
			// {
			// 	cout<<"-1\n";
			// 	continue;
			// }
			cout<<ans.size()<<'\n';
			// assert(ans.size()<=3*n/2);
			auto a=b;
			for (auto [x,y]:ans)
			{
				cout<<x+1<<' '<<y+1<<'\n';
				assert(a[x].size());
				assert(a[y].size()<=1);
				if (a[y].size()) assert(a[y][0]==a[x].back());
				a[y].push_back(a[x].back()); a[x].pop_back();
			}
			for (i=0; i<m; i++) if (a[i].size())
			{
				assert(a[i].size()==2&&a[i][0]==a[i][1]);
			}
		}
	}
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3444kb

input:

2 3
2 1 2
2 1 2
0
1 1
2 1 1
3 4
2 1 3
2 2 3
1 1
1 2

output:

3
2 3
1 3
2 1
0
-1

result:

ok 3 cases passed. max #moves/#balls = 1.500000000

Test #2:

score: 0
Accepted
time: 1ms
memory: 3516kb

input:

1 2
1 1
1 1
1 3
1 1
0
1 1
1 4
1 1
1 1
0
0
1 1
2 1 1
1 2
2 1 1
0
1 3
0
0
2 1 1

output:

1
2 1
1
3 1
1
2 1
0
0
0

result:

ok 6 cases passed. max #moves/#balls = 1.000000000

Test #3:

score: 0
Accepted
time: 1ms
memory: 3420kb

input:

2 4
1 1
1 2
1 2
1 1
2 5
1 1
1 2
0
1 1
1 2
2 6
0
1 1
0
1 1
1 2
1 2
2 4
1 2
1 1
1 1
1 2
2 5
1 1
0
1 2
1 2
1 1
2 6
1 2
0
1 1
0
1 1
1 2
2 4
1 1
1 2
1 2
1 1
2 5
0
1 2
1 1
1 1
1 2
2 6
1 1
0
1 2
1 2
0
1 1
2 3
2 2 1
1 1
1 2
2 4
2 2 1
1 1
0
1 2
2 5
1 1
0
1 2
2 1 2
0
2 3
1 2
2 1 2
1 1
2 4
1 1
2 2 1
1 2
0
2 5
...

output:

2
4 1
3 2
2
4 1
5 2
2
4 2
6 5
2
4 1
3 2
2
5 1
4 3
2
6 1
5 3
2
4 1
3 2
2
5 2
4 3
2
6 1
4 3
2
1 2
3 1
2
1 2
4 1
2
4 3
1 4
2
2 1
3 2
2
2 1
3 2
2
1 3
4 1
-1
3
3 1
2 1
3 2
3
4 3
2 3
4 2
-1
3
2 3
1 2
1 3
3
2 4
1 2
1 4
1
3 2
1
4 3
1
4 1
0
0
0

result:

ok 27 cases passed. max #moves/#balls = 1.500000000

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 3424kb

input:

3 6
1 1
1 2
1 2
1 3
1 3
1 1
3 7
1 3
0
1 2
1 2
1 1
1 1
1 3
3 8
0
1 3
1 2
0
1 1
1 1
1 2
1 3
3 6
1 3
1 3
1 2
1 1
1 1
1 2
3 7
1 1
1 3
1 1
1 2
1 2
1 3
0
3 8
1 1
1 2
0
1 3
1 2
0
1 3
1 1
3 6
1 3
1 1
1 2
1 3
1 2
1 1
3 7
1 1
1 2
0
1 1
1 3
1 3
1 2
3 8
1 2
1 1
1 3
1 2
0
1 3
0
1 1
3 6
1 2
1 2
1 3
1 1
1 1
1 3
3 ...

output:

3
6 1
3 2
5 4
3
7 1
4 3
6 5
3
8 2
7 3
6 5
3
2 1
6 3
5 4
3
3 1
6 2
5 4
3
8 1
5 2
7 4
3
4 1
6 2
5 3
3
4 1
7 2
6 5
3
4 1
8 2
6 3
3
2 1
6 3
5 4
3
5 2
6 3
7 4
3
2 1
4 3
8 5
3
6 1
5 2
4 3
3
3 1
7 4
6 5
3
5 2
8 4
7 6
3
2 1
6 3
5 4
3
3 1
7 2
6 5
3
4 2
7 3
8 6
3
5 1
3 2
6 4
3
5 1
3 2
7 4
3
6 1
8 4
7 5
3
5 1
...

result:

wrong answer Should find solution [Case 89]
English 繁體中文 简体中文

Server Time: 2024-11-30 02:27:01 | OpenSource Project