QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#393354 | #6545. Connect the Dots | Nahidameow | WA | 0ms | 3888kb | C++20 | 1.9kb | 2024-04-18 15:34:23 | 2024-04-18 15:34:24 |
Judging History
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.