QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#82006#2830. Data StructureAHSFNU_team_0WA 31ms16788kbC++143.9kb2023-02-26 21:03:162023-02-26 21:03:18

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 21:03:18]
  • 评测
  • 测评结果：WA
  • 用时：31ms
  • 内存：16788kb
查看
  • [2023-02-26 21:03:16]
  • 提交

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],sk[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(cnt>500000){
		printf("  %d %d\n",n,m);
		for(int i=1;i<=m;++i){
			for(auto v:sk[i])printf(" %d",v);
			puts("");
		}
		exit(0);
	}
	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);
	}
	pos[stk[x].back()]=y;
	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(){
	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);
			sk[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;
				sk[i][j]=x;
			}
		}
		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(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;
		}
		bool ok=0;
		for(int i=1;i<=m;++i){
			if(stk[i].size()==1)ans=0;
			if(stk[i].size()==2 && stk[i][0]!=opp(stk[i][1]))ok=1;
		}
		if(!ans){puts("-1");continue;}
		if(ok){
			for(int i=1;i<=m;++i){
				if(stk[i].empty())continue;
				if(stk[i][0]==opp(stk[i][1]))continue;
				if(ept.empty()){ans=0;break;}
				oper(i,*ept.begin());
				while(1){
					bool fg=0;
					for(int i=0;i<2;++i){
						for(int j=0,u;j<2;++j){
							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)break;
				}
			}
		}
		if(!ans){puts("-1");continue;}
		if(n>=4)continue;
		printf("%d\n",cnt);
		for(int i=1;i<=cnt;++i)
			printf("%d %d\n",ax[i],ay[i]);
	}
	return 0;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 5ms
memory: 12828kb

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: 2ms
memory: 12856kb

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
3
1 3
2 1
2 3
3
1 3
2 1
2 3
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: 0
Accepted
time: 8ms
memory: 13036kb

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

result:

ok 180 cases passed. max #moves/#balls = 1.333333333

Test #5:

score: -100
Wrong Answer
time: 31ms
memory: 16788kb

input:

4 8
1 3
1 3
1 4
1 1
1 2
1 1
1 4
1 2
4 9
1 3
0
1 2
1 1
1 4
1 1
1 4
1 2
1 3
4 10
1 1
1 3
1 3
1 2
1 2
0
1 1
1 4
1 4
0
4 8
1 4
1 3
1 2
1 2
1 1
1 4
1 1
1 3
4 9
1 4
1 3
1 1
1 3
1 4
1 2
1 1
1 2
0
4 10
1 4
1 1
1 2
1 3
0
0
1 2
1 1
1 3
1 4
4 8
1 2
1 4
1 3
1 4
1 2
1 3
1 1
1 1
4 9
1 1
1 4
1 3
1 2
1 3
1 2
0
1 4
...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
  4 6
 4 3
 2 1
 8 5


 6 7

result:

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

Server Time: 2024-11-30 00:39:52 | OpenSource Project