QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#81934#2830. Data StructureAHSFNU_team_0WA 4ms9456kbC++143.4kb2023-02-26 18:39:232023-02-26 18:39:26

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-26 18:39:26]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:9456kb
  • [2023-02-26 18:39:23]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,vis[400005],pos[400005],ans;
int ax[500005],ay[500005],cnt;
vector<int> stk[200005];
set<int> s[2][2],t[3],ept;
inline int opp(int u){
	if(u>n)return u-n;
	return u+n;
}
inline void ins(int u,int v){
	if(u!=stk[pos[u]].back())return;
	if(v!=stk[pos[v]].back())return;
	if(u>v)swap(u,v);
	if(stk[pos[u]].size()<2 || stk[pos[v]].size()<2)
		s[stk[pos[u]].size()==2][stk[pos[v]].size()==2].insert(u);
	else{
		if(stk[pos[opp(stk[pos[u]][0])]].size()<2)t[0].insert(u);
		else if(stk[pos[opp(stk[pos[v]][0])]].size()<2)t[0].insert(u);
		else if(pos[opp(stk[pos[u]][0])]==pos[v])t[1].insert(u);
		else t[2].insert(u);
	}
}
inline void del(int u,int v){
	if(u!=stk[pos[u]].back())return;
	if(v!=stk[pos[v]].back())return;
	if(u>v)swap(u,v);
	if(stk[pos[u]].size()<2 || stk[pos[v]].size()<2)
		s[stk[pos[u]].size()==2][stk[pos[v]].size()==2].erase(u);
	else{
		if(stk[pos[opp(stk[pos[u]][0])]].size()<2)t[0].erase(u);
		else if(stk[pos[opp(stk[pos[v]][0])]].size()<2)t[0].erase(u);
		else if(pos[opp(stk[pos[u]][0])]==pos[v])t[1].erase(u);
		else t[2].erase(u);
	}
}
inline void oper(int x,int y){
	ax[++cnt]=x,ay[cnt]=y;
	if(stk[x].empty())ept.erase(x);
	if(stk[y].empty())ept.erase(y);
	for(int i=0,u,v;i<(int)stk[x].size();++i){
		u=stk[x][i],v=opp(u);
		del(u,v);
	}
	for(int i=0,u,v;i<(int)stk[y].size();++i){
		u=stk[y][i],v=opp(u);
		del(u,v);
	}
	stk[y].push_back(stk[x].back());
	stk[x].pop_back();
	if(stk[x].empty())ept.insert(x);
	if(stk[y].empty())ept.insert(y);
	for(int i=0,u,v;i<(int)stk[x].size();++i){
		u=stk[x][i],v=opp(u);
		ins(u,v);
	}
	for(int i=0,u,v;i<(int)stk[y].size();++i){
		u=stk[y][i],v=opp(u);
		ins(u,v);
	}
}
inline bool work(int u){
	if(ept.empty())return 0;
	int t=*ept.begin();
	oper(pos[u],t),oper(pos[u+n],t);
	return 1;
}
int main(){
	int tt=0;
	while(~scanf("%d%d",&n,&m)){
		for(int i=1;i<=m;++i)stk[i].clear();
		for(int i=1;i<=n;++i)vis[i]=0;
		for(int i=1,k;i<=m;++i){
			scanf("%d",&k);
			stk[i].resize(k);
			for(int j=0,x;j<k;++j){
				scanf("%d",&x);
				if(vis[x])x+=n;
				else vis[x]=1;
				stk[i][j]=x,pos[x]=i;
			}
		}
		if(tt==20){
			printf("  %d %d\n",n,m);
			for(int i=1;i<=m;++i){
				for(auto v:stk[i])printf("%d ",v);
				puts("");
			}
			return 0;
		}
		for(int i=0;i<2;++i)
			for(int j=0;j<2;++j)s[i][j].clear();
		for(int i=0;i<3;++i)t[i].clear();
		ept.clear();
		for(int i=1,u,v;i<=m;++i){
			if(stk[i].empty()){
				ept.insert(i);
				continue;
			}
			u=stk[i].back(),v=opp(u);
			if(stk[pos[v]].back()==v)ins(u,v);
		}
		cnt=0,ans=1;
		while(1){
			bool fg=0;
			for(int i=0;i<2;++i){
				for(int j=0,u;j<2;++j){
					if(i==1 && j==1)continue;
					if(s[i][j].empty())continue;
					u=*s[i][j].begin();
					if(stk[pos[u]].size()==1)oper(pos[u+n],pos[u]);
					else oper(pos[u],pos[u+n]);
					fg=1;break;
				}
				if(fg)break;
			}
			if(fg)continue;
			for(int i=0;i<3;++i){
				if(t[i].empty())continue;
				if(work(*t[i].begin())){fg=1;break;}
				else{fg=0;break;}
			}
			if(!fg)break;
		}
		for(int i=1;i<=m;++i){
			if(stk[i].size()==0)continue;
			if(stk[i].size()==1)ans=0;
			if(stk[i].size()==2 && stk[i][0]!=opp(stk[i][1]))ans=0;
		}
		if(!ans){puts("-1");continue;}
		printf("%d\n",cnt);
		for(int i=1;i<=cnt;++i)
			printf("%d %d\n",ax[i],ay[i]);
	}
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 4ms
memory: 8164kb

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
1 3
2 3
2 1
0
-1

result:

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

Test #2:

score: 0
Accepted
time: 0ms
memory: 8204kb

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
Wrong Answer
time: 4ms
memory: 9456kb

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
3 2
4 1
2
5 1
4 3
2
5 3
6 1
2
4 1
3 2
2
4 3
5 2
2
6 1
4 3
2
1 2
3 1
2
1 2
4 1
2
4 3
4 1
2
2 1
3 2
2
2 1
3 2
2
1 3
4 1
-1
3
2 1
3 1
3 2
3
2 1
4 1
4 2
-1
-1
-1
1
3 2
1
4 3
1
4 1
0
0
0

result:

wrong answer Should find solution [Case 20]