QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#246257#2830. Data Structurenameless_story#RE 1ms3428kbC++203.2kb2023-11-10 18:01:062023-11-10 18:01:06

Judging History

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

  • [2023-11-10 18:01:06]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3428kb
  • [2023-11-10 18:01:06]
  • 提交

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()
int main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	int n,m,i,j;
	while (cin>>n>>m)
	{
		vector<vector<int>> a(m);
		vector<int> pos(n);
		vector<int> empty;
		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);
		}
		auto b=a;
		auto solve=[&]() -> vector<pair<int,int>>
			{
				vector<pair<int,int>> ans;
				auto one=[&](int i)
					{
						assert(a[i].size()==1);
						int x=a[i][0];
						int j=pos[x]-i;
						assert(a[j].size());
						if (a[j].size()==2)
						{
							if (a[j][1]==x)
							{
								ans.push_back({j,i});
								a[i]={x,x};
								a[j].pop_back();
								pos[x]=i*2;
								return;
							}
							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;
						}
						empty.push_back(j);
						ans.push_back({j,i});
						a[j]={ };
						a[i]={x,x};
						pos[x]=i*2;
					};
				auto twoup=[&](int i)
					{
						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();
						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]={ };
					};
				auto two=[&](int i)
					{
						int x=a[i][1];
						int j=pos[x]-i;
						assert(a[j].size()==2&&a[j][0]==x);
						int e1=empty.back(); empty.pop_back();
						ans.push_back({j,e1});
						pos[a[j].back()]+=e1-j;
						a[e1]={a[j].back()};
						a[j]={x,x};
						pos[x]=j*2;
						a[i].pop_back();
						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) one(i);
				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);
				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())
				{
					if (a[i].size()!=2) return {{-1,-1}};
					if (a[i][0]!=a[i][1]) return {{-1,-1}};
				}
				return ans;
			};
		auto ans=solve();
		if (ans==vector{pair{-1,-1}}) cout<<"-1\n";
		else
		{
			cout<<ans.size()<<'\n';
			auto a=b;
			for (auto [x,y]:ans)
			{
				cout<<x+1<<' '<<y+1<<'\n';
				assert(a[x].size()&&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]);
			}
		}
	}
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3428kb

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: 3396kb

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: -100
Runtime Error

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:


result: