QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#168815#6545. Connect the DotsPhantomThresholdWA 1ms3848kbC++203.5kb2023-09-08 22:38:392023-09-08 22:38:40

Judging History

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

  • [2023-09-08 22:38:40]
  • 评测
  • 测评结果：WA
  • 用时：1ms
  • 内存：3848kb
查看
  • [2023-09-08 22:38:39]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int main()
{
	ios_base::sync_with_stdio(false);
//	cin.tie(0);
	int T;
	cin>>T;
	while(T--)
	{
		int n,m;
		cin>>n>>m;
		vector<pair<int,int>> ans;
		vector<int> now;
		vector<int> c(n+5);
		int nowc=0;
		for(int i=1;i<=n;i++)
		{
			cin>>c[i];
//			cerr<<"? "<<i<<endl;
			if(nowc==0)
			{
				now.push_back(i);
				nowc++;
			}
			else if(nowc==1)
			{
				if(c[i]==c[now.back()])
					now.push_back(i);
				else
				{
					nowc++;
					int u=0;
					while(not now.empty())
					{
						u=now.back();now.pop_back();
						ans.emplace_back(u,i);
					}
					now.push_back(u);
					now.push_back(i);
				}
			}
			else if(nowc==2)
			{
				int bid=now.size()-1;
				if(c[i]==c[now[bid]])
				{
					ans.emplace_back(now[bid-1],i);
					now.pop_back();
					now.push_back(i);
				}
				else if(c[i]==c[now[bid-1]])
				{
					ans.emplace_back(now[bid],i);
					now.push_back(i);
				}
				else
				{
					nowc++;
					int u=0;
					while(now.size()>1u)
					{
						u=now.back();now.pop_back();
						ans.emplace_back(u,i);
					}
					now.push_back(u);
					now.push_back(i);
				}
			}
			else
			{
				if(c[i]!=c[now[0]] and c[i]!=c[now[1]] and c[i]!=c[now[2]])
				{
					if(now.size()==4u)
					{
						ans.emplace_back(now.back(),i);
						now.pop_back();
					}
					ans.emplace_back(now.back(),i);now.pop_back();
					ans.emplace_back(now.back(),i);now.pop_back();
					now.push_back(i);
				}
				else
				{
					if(now.size()==3u)
					{
						if(c[i]==c[now[2]])
						{
							ans.emplace_back(now.back(),i);
							now.pop_back();
							now.push_back(i);
						}
						else
						{
							ans.emplace_back(now.back(),i);
							now.push_back(i);
						}
					}
					else
					{
						if(c[now[3]]==c[now[0]])
						{
							if(c[i]==c[now[0]])
							{
								ans.emplace_back(now[2],i);
								now.pop_back();
								now.push_back(i);
							}
							else if(c[i]==c[now[1]])
							{
								ans.emplace_back(now[2],i);
								ans.emplace_back(now[3],i);
								now.pop_back();
								now.push_back(i);
							}
							else
							{
								ans.emplace_back(now[1],now[3]);
								ans.emplace_back(now[1],i);
								ans.emplace_back(now[3],i);
								now.pop_back();
								now.pop_back();
								now.push_back(i);
							}
						}
						else if(c[now[3]]==c[now[1]])
						{
							if(c[i]==c[now[0]])
							{
								ans.emplace_back(now[2],i);
								ans.emplace_back(now[3],i);
								now.pop_back();
								now.push_back(i);
							}
							else if(c[i]==c[now[1]])
							{
								ans.emplace_back(now[2],i);
								now.pop_back();
								now.push_back(i);
							}
							else
							{
								ans.emplace_back(now[0],now[2]);
								ans.emplace_back(now[0],now[3]);
								ans.emplace_back(now[3],i);
								now[1]=now[3];
								now.pop_back();
								now.pop_back();
								now.push_back(i);
							}
						}
					}
				}
			}
		}
		//fin
		if(nowc==2)
		{
			int i=now.back();now.pop_back();now.pop_back();
			while(not now.empty())
			{
				if(c[i]!=c[now.back()])
					ans.emplace_back(now.back(),i);
				now.pop_back();
			}
		}
		else
		{
			ans.emplace_back(now[0],now[2]);
			if(now.size()==4u)
			{
				if(now.front()!=now.back())ans.emplace_back(now.front(),now.back());
			}
		}
		cout<<ans.size()<<"\n";
		for(auto [u,v]:ans)
			cout<<u<<' '<<v<<"\n";
	}
	return 0;
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

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

result:

ok all 3 test passed

Test #2:

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

input:

1
2 2
1 2

output:

1
1 2

result:

ok all 1 test passed

Test #3:

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

input:

10
5 2
2 2 2 1 2
5 2
2 1 2 1 2
5 2
1 2 2 2 1
5 2
2 1 2 1 1
5 2
1 1 1 2 1
5 2
1 2 2 1 2
5 2
2 1 1 2 2
5 2
2 2 2 1 1
5 2
1 1 2 1 2
5 2
1 2 2 2 1

output:

4
3 4
2 4
1 4
4 5
5
1 2
2 3
3 4
4 5
2 5
4
1 2
1 3
1 4
4 5
5
1 2
2 3
3 4
3 5
1 5
4
3 4
2 4
1 4
4 5
5
1 2
1 3
3 4
4 5
1 5
4
1 2
1 3
3 4
3 5
4
3 4
2 4
1 4
1 5
5
2 3
1 3
3 4
4 5
1 5
4
1 2
1 3
1 4
4 5

result:

ok all 10 test passed

Test #4:

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

input:

10
7 2
1 2 1 1 1 2 1
7 2
1 1 2 1 2 1 2
7 2
2 2 1 1 2 1 1
7 2
1 1 1 2 2 1 1
7 2
1 2 2 1 2 2 1
7 2
2 1 2 2 2 2 1
7 2
1 2 1 2 2 2 2
7 2
2 2 1 2 1 2 1
7 2
2 1 1 2 1 2 2
7 2
2 2 1 2 1 1 2

output:

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

result:

ok all 10 test passed

Test #5:

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

input:

10
9 2
1 1 1 2 1 2 2 1 2
9 2
1 2 1 1 2 2 2 2 1
9 2
2 1 2 1 1 2 1 2 1
9 2
1 1 2 1 1 1 1 2 2
9 2
1 1 2 2 1 2 1 2 2
9 2
2 2 1 2 1 2 2 2 2
9 2
1 1 2 2 2 1 2 1 2
9 2
1 1 2 1 1 2 2 2 2
9 2
1 1 1 1 2 1 1 2 1
9 2
2 1 2 2 1 1 2 2 1

output:

10
3 4
2 4
1 4
4 5
5 6
5 7
7 8
8 9
5 9
1 9
9
1 2
2 3
2 4
4 5
4 6
4 7
4 8
8 9
2 9
11
1 2
2 3
3 4
3 5
5 6
6 7
7 8
8 9
6 9
3 9
1 9
9
2 3
1 3
3 4
3 5
3 6
3 7
7 8
7 9
1 9
10
2 3
1 3
1 4
4 5
5 6
6 7
7 8
7 9
5 9
1 9
9
2 3
1 3
3 4
4 5
5 6
5 7
5 8
5 9
3 9
10
2 3
1 3
1 4
1 5
5 6
6 7
7 8
8 9
6 9
1 9
9
2 3
1 3
...

result:

ok all 10 test passed

Test #6:

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

input:

1
5 2
1 1 2 2 1

output:

4
2 3
1 3
1 4
4 5

result:

ok all 1 test passed

Test #7:

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

input:

1
7 2
2 1 1 2 1 1 2

output:

7
1 2
1 3
3 4
4 5
4 6
6 7
3 7

result:

ok all 1 test passed

Test #8:

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

input:

1
9 2
2 1 1 2 1 1 1 2 2

output:

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

result:

ok all 1 test passed

Test #9:

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

input:

4
20 2
2 1 1 2 1 2 1 1 2 1 1 1 1 2 2 2 1 1 2 2
20 2
2 1 2 2 2 1 1 2 2 2 1 2 2 2 2 1 2 2 1 2
20 2
2 2 1 1 2 2 1 1 1 1 1 2 1 1 2 2 1 2 1 1
20 2
2 1 2 2 2 1 2 2 1 1 1 2 1 2 2 1 2 1 1 2

output:

23
1 2
1 3
3 4
4 5
5 6
6 7
6 8
8 9
9 10
9 11
9 12
9 13
13 14
13 15
13 16
16 17
16 18
18 19
18 20
13 20
8 20
5 20
3 20
23
1 2
2 3
2 4
2 5
5 6
5 7
7 8
7 9
7 10
10 11
11 12
11 13
11 14
11 15
15 16
16 17
16 18
18 19
19 20
16 20
11 20
7 20
2 20
23
2 3
1 3
1 4
4 5
4 6
6 7
6 8
6 9
6 10
6 11
11 12
12 13
12 ...

result:

ok all 4 test passed

Test #10:

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

input:

4
100 2
2 2 2 1 2 1 1 1 1 2 2 1 2 2 2 1 2 2 2 2 1 1 1 2 2 1 1 2 1 1 2 1 2 2 1 1 1 2 1 2 1 1 2 1 2 1 2 1 2 1 1 1 1 2 1 1 1 2 2 2 1 2 2 2 1 1 1 2 1 2 1 2 2 1 2 2 1 1 2 1 1 1 1 2 2 1 2 1 1 2 2 1 2 2 1 2 1 2 2 2
100 2
2 1 1 1 1 1 2 2 2 1 2 1 2 2 1 2 2 1 1 1 1 2 1 1 1 2 2 1 1 2 1 1 2 1 1 2 1 1 1 1 1 2 1 ...

output:

126
3 4
2 4
1 4
4 5
5 6
5 7
5 8
5 9
9 10
9 11
11 12
12 13
12 14
12 15
15 16
16 17
16 18
16 19
16 20
20 21
20 22
20 23
23 24
23 25
25 26
25 27
27 28
28 29
28 30
30 31
31 32
32 33
32 34
34 35
34 36
34 37
37 38
38 39
39 40
40 41
40 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
49 51
49 52
49 53
53...

result:

ok all 4 test passed

Test #11:

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

input:

1
100 2
2 2 1 1 2 2 2 1 1 2 1 1 1 2 2 1 2 2 2 1 1 2 2 1 1 2 2 2 1 2 1 1 2 1 1 2 2 1 2 1 1 2 1 2 2 1 2 2 2 2 1 2 1 2 1 1 2 1 1 1 1 1 2 2 2 1 1 2 1 2 2 2 2 1 1 2 2 2 1 1 2 2 2 1 2 2 1 2 1 2 1 2 2 2 1 2 2 2 1 1

output:

125
2 3
1 3
1 4
4 5
4 6
4 7
7 8
7 9
9 10
10 11
10 12
10 13
13 14
13 15
15 16
16 17
16 18
16 19
19 20
19 21
21 22
21 23
23 24
23 25
25 26
25 27
25 28
28 29
29 30
30 31
30 32
32 33
33 34
33 35
35 36
35 37
37 38
38 39
39 40
39 41
41 42
42 43
43 44
43 45
45 46
46 47
46 48
46 49
46 50
50 51
51 52
52 53
5...

result:

ok all 1 test passed

Test #12:

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

input:

1
100 2
1 2 2 1 1 2 2 1 1 2 2 1 1 2 2 1 1 2 2 1 1 2 2 1 1 2 2 1 1 2 2 1 1 2 2 1 1 2 2 1 1 2 2 1 1 2 2 1 1 2 2 1 1 2 2 1 1 2 2 1 1 2 2 1 1 2 2 1 1 2 2 1 1 2 2 1 1 2 2 1 1 2 2 1 1 2 2 1 1 2 2 1 1 2 2 1 1 2 2 1

output:

123
1 2
1 3
3 4
3 5
5 6
5 7
7 8
7 9
9 10
9 11
11 12
11 13
13 14
13 15
15 16
15 17
17 18
17 19
19 20
19 21
21 22
21 23
23 24
23 25
25 26
25 27
27 28
27 29
29 30
29 31
31 32
31 33
33 34
33 35
35 36
35 37
37 38
37 39
39 40
39 41
41 42
41 43
43 44
43 45
45 46
45 47
47 48
47 49
49 50
49 51
51 52
51 53
53...

result:

ok all 1 test passed

Test #13:

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

input:

1
200 2
1 1 1 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 2 2 2 ...

output:

208
3 4
2 4
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
13 14
13 15
13 16
13 17
13 18
13 19
13 20
13 21
13 22
13 23
23 24
23 25
23 26
23 27
23 28
23 29
23 30
23 31
23 32
23 33
33 34
33 35
33 36
33 37
33 38
33 39
33 40
33 41
33 42
33 43
43 44
43 45
43 46
43 47
43 48
43 49
43 50
43 51
43 52
43 53
53 5...

result:

ok all 1 test passed

Test #14:

score: -100
Wrong Answer
time: 1ms
memory: 3816kb

input:

4
7 3
2 2 3 1 3 1 1
7 3
3 1 2 2 3 1 3
7 3
2 1 3 3 2 3 2
7 3
3 2 3 1 3 1 3

output:

9
2 3
1 3
3 4
4 5
1 4
1 5
5 6
6 7
1 7
10
1 2
2 3
3 4
4 5
4 6
5 6
4 7
6 7
1 4
1 7
10
1 2
2 3
3 4
4 5
2 5
2 6
5 6
6 7
1 6
1 7
11
1 2
2 3
3 4
2 4
4 5
2 5
2 6
5 6
6 7
1 6
1 7

result:

wrong answer TC #1: wire should connect two houses using different company.
English 繁體中文 简体中文

Server Time: 2024-12-02 21:59:02 | OpenSource Project