QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#393354#6545. Connect the DotsNahidameowWA 0ms3888kbC++201.9kb2024-04-18 15:34:232024-04-18 15:34:24

Judging History

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

  • [2024-04-18 15:34:24]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3888kb
  • [2024-04-18 15:34:23]
  • 提交

answer

#include<bits/stdc++.h>
#define pd push_back
#define all(A) A.begin(),A.end()
#define lower_bound lb
#define ve std::vector
typedef long long ll;
typedef long long ll;
typedef __int128 Int;
typedef unsigned long long ul;
typedef long double LD;
bool FileIfstream(std::string name){
	std::ifstream f(name.c_str());
	return f.good();
}
namespace Math{
	ll QP(ll x,ll y,ll mod){ll ans=1;for(;y;y>>=1,x=x*x%mod)if(y&1)ans=ans*x%mod;return ans;}
	ll inv(ll x,ll mod){return QP(x,mod-2,mod);}
}
const int N=2e5+10;
const int mod=998244353;
void solve(){
	//don't forget to open long long
	int n,m;std::cin>>n>>m;
	ve<int>v(n+1);
	ve<std::array<int,2>>ans;
	for(int i=1;i<=n;i++)std::cin>>v[i];
	for(int i=1;i<n;i++)
		if(v[i]!=v[i+1])ans.pd({i,i+1});
	ve<bool>del(n+1);
	auto special=[&](int x)->void{
		int L=x,R=x;
		for(int i=x-1;i>=1;i--)
			if(!del[i]){if(L^x)ans.pd({i,x});L=i;}
		for(int i=x+1;i<=n;i++)
			if(!del[i]){if(R^x)ans.pd({x,i});R=i;}
		if(v[L]!=v[R]&&L!=x&&R!=x)ans.pd({L,R});
	};
	ve<int>st;
	ve<int>cnt(m+1);
	for(int i=1;i<=n;i++)
		cnt[v[i]]++;
	for(int i=1;i<=n;i++){
		while(st.size()>=2&&v[st[st.size()-2]]!=v[i]){
			if(cnt[v[i]]==1){
				special(i);
				st.clear();
				goto flg;
			}
			ans.pd({st[st.size()-2],i});
			del[st.back()]=true;
			--cnt[v[st.back()]];
			st.pop_back();
		}
		st.pd(i);
	}
	for(int i=4;i<=st.size();i+=2)
		ans.pd({st[0],st[i-1]});
	flg:;
	sort(all(ans));ans.erase(unique(all(ans)),ans.end());
	std::cout<<ans.size()<<'\n';
	for(auto &p:ans)
		std::cout<<p[0]<<' '<<p[1]<<'\n';
}
int main(){
#ifndef ONLINE_JUDGE
	if(!FileIfstream("IO.in")){
		freopen("IO.in","w",stdout);
		return 0;
	}
	freopen("IO.in","r",stdin);
	freopen("IO.out","w",stdout);
#endif
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	int T=1;
	std::cin>>T;
	while(T--)solve();

	return 0;
}




詳細信息

Test #1:

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

input:

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

output:

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

result:

ok all 3 test passed

Test #2:

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

input:

1
2 2
1 2

output:

1
1 2

result:

ok all 1 test passed

Test #3:

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

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

result:

ok all 10 test passed

Test #4:

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

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

result:

ok all 10 test passed

Test #5:

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

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

result:

ok all 10 test passed

Test #6:

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

input:

1
5 2
1 1 2 2 1

output:

4
1 3
1 4
2 3
4 5

result:

ok all 1 test passed

Test #7:

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

input:

1
7 2
2 1 1 2 1 1 2

output:

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

result:

ok all 1 test passed

Test #8:

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

input:

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

output:

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

result:

ok all 1 test passed

Test #9:

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

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
1 5
1 8
1 13
1 18
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
23
1 2
1 7
1 11
1 16
1 19
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
23
1 3
1 4
1 11
1 14
1 17
1 20
2 3
4 5
4 6
6 7
6 8
6 9
6 10
6 11
1...

result:

ok all 4 test passed

Test #10:

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

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
1 4
1 9
1 12
1 16
1 23
1 27
1 30
1 32
1 37
1 39
1 42
1 44
1 46
1 48
1 53
1 57
1 61
1 67
1 69
1 71
1 74
1 78
1 83
1 86
1 89
1 92
1 95
1 97
2 4
3 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
...

result:

ok all 4 test passed

Test #11:

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

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
1 3
1 4
1 9
1 13
1 16
1 21
1 25
1 29
1 32
1 35
1 38
1 41
1 43
1 46
1 51
1 53
1 56
1 62
1 67
1 69
1 75
1 80
1 84
1 87
1 89
1 91
1 95
1 100
2 3
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 ...

result:

ok all 1 test passed

Test #12:

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

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
1 7
1 11
1 15
1 19
1 23
1 27
1 31
1 35
1 39
1 43
1 47
1 51
1 55
1 59
1 63
1 67
1 71
1 75
1 79
1 83
1 87
1 91
1 95
1 99
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 ...

result:

ok all 1 test passed

Test #13:

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

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
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 33
1 53
1 73
1 93
1 113
1 133
1 153
1 173
1 193
2 4
3 4
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...

result:

ok all 1 test passed

Test #14:

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

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

result:

wrong answer output = 8, answer = 9.