QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#211067 | #6545. Connect the Dots | ucup-team1004 | WA | 1ms | 6168kb | C++14 | 1.9kb | 2023-10-12 07:35:05 | 2023-10-12 07:35:05 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
template<typename T>
ostream& operator << (ostream &out,const vector<T>&x){
if(x.empty())return out<<"[]";
out<<'['<<x[0];
for(int len=x.size(),i=1;i<len;i++)out<<','<<x[i];
return out<<']';
}
template<typename T>
vector<T> ary(const T *a,int l,int r){
return vector<T>{a+l,a+1+r};
}
template<typename T>
void debug(T x){
cerr<<x<<'\n';
}
template<typename T,typename ...S>
void debug(T x,S ...y){
cerr<<x<<' ',debug(y...);
}
const int N=2e5+10;
int T,n,m,a[N],cnt[N],pre[N],nex[N];
bool chk(int x){
return pre[x]&&nex[x]<=n&&a[pre[x]]!=a[nex[x]];
}
void del(int x){
nex[pre[x]]=nex[x],pre[nex[x]]=pre[x];
}
void get(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=n;i++)cnt[a[i]]++;
for(int i=0;i<=n;i++)nex[i]=i+1,pre[i+1]=i;
set<int>s;
for(int i=1;i<=n;i++)if(chk(i))s.insert(i);
vector<pair<int,int> >ans;
ans.clear();
for(int i=1;i<n;i++){
if(a[i]^a[i+1])ans.push_back({i,i+1});
}
for(int t=n-2;t--;){
if(!s.empty()){
int i=*s.begin();
if(cnt[a[i]]==1){
for(;pre[i]!=1;del(pre[i])){
ans.push_back({pre[pre[i]],i});
}
for(;nex[i]!=n;del(nex[i])){
ans.push_back({i,nex[nex[i]]});
}
if(chk(i)){
ans.push_back({pre[i],nex[i]});
}
break;
}else{
s.erase(i);
if(chk(pre[i]))s.erase(pre[i]);
if(chk(nex[i]))s.erase(nex[i]);
ans.push_back({pre[i],nex[i]});
del(i);
if(chk(pre[i]))s.insert(pre[i]);
if(chk(nex[i]))s.insert(nex[i]);
}
}else{
int i=nex[1];
del(i);
if(chk(pre[i]))s.insert(pre[i]);
if(chk(nex[i]))s.insert(nex[i]);
}
}
printf("%lu\n",ans.size());
for(auto x:ans)printf("%d %d\n",x.first,x.second);
}
void clr(){
for(int i=1;i<=m;i++)cnt[i]=0;
}
int main(){
for(scanf("%d",&T);T--;clr())get();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 4132kb
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: 0ms
memory: 5880kb
input:
1 2 2 1 2
output:
1 1 2
result:
ok all 1 test passed
Test #3:
score: 0
Accepted
time: 0ms
memory: 6136kb
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 4 5 2 4 1 4 5 1 2 2 3 3 4 4 5 1 4 4 1 2 4 5 1 3 1 4 5 1 2 2 3 3 4 3 5 1 5 4 3 4 4 5 2 4 1 4 5 1 2 3 4 4 5 1 3 1 5 4 1 2 3 4 1 3 3 5 4 3 4 2 4 1 4 1 5 5 2 3 3 4 4 5 1 3 1 5 4 1 2 4 5 1 3 1 4
result:
ok all 10 test passed
Test #4:
score: 0
Accepted
time: 1ms
memory: 5936kb
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 5 6 6 7 2 4 2 5 1 6 8 2 3 3 4 4 5 5 6 6 7 1 3 1 5 1 7 7 2 3 4 5 5 6 1 3 1 4 5 7 1 7 6 3 4 5 6 2 4 1 4 1 5 5 7 7 1 2 3 4 4 5 6 7 1 3 4 6 1 6 7 1 2 2 3 6 7 2 4 2 5 2 6 1 7 7 1 2 2 3 3 4 3 5 3 6 3 7 1 7 8 2 3 3 4 4 5 5 6 6 7 1 3 1 5 1 7 7 1 2 3 4 4 5 5 6 1 3 5 7 1 5 7 2 3 3 4 4 5 6 7 1 3 4 6 ...
result:
ok all 10 test passed
Test #5:
score: 0
Accepted
time: 1ms
memory: 6168kb
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 4 5 5 6 7 8 8 9 2 4 1 4 5 7 1 7 1 9 9 1 2 2 3 4 5 8 9 2 4 4 6 4 7 4 8 1 8 11 1 2 2 3 3 4 5 6 6 7 7 8 8 9 3 5 1 5 1 7 1 9 9 2 3 3 4 7 8 1 3 3 5 3 6 3 7 7 9 1 9 10 2 3 4 5 5 6 6 7 7 8 1 3 1 4 7 9 1 6 1 9 9 2 3 3 4 4 5 5 6 1 3 5 7 5 8 5 9 1 5 10 2 3 5 6 6 7 7 8 8 9 1 3 1 4 1 5 1 7 1 9 9 2 3 3 4 ...
result:
ok all 10 test passed
Test #6:
score: 0
Accepted
time: 1ms
memory: 5880kb
input:
1 5 2 1 1 2 2 1
output:
4 2 3 4 5 1 3 1 4
result:
ok all 1 test passed
Test #7:
score: 0
Accepted
time: 0ms
memory: 3912kb
input:
1 7 2 2 1 1 2 1 1 2
output:
7 1 2 3 4 4 5 6 7 1 3 4 6 1 6
result:
ok all 1 test passed
Test #8:
score: 0
Accepted
time: 0ms
memory: 5832kb
input:
1 9 2 2 1 1 2 1 1 1 2 2
output:
9 1 2 3 4 4 5 7 8 1 3 4 6 4 7 7 9 1 7
result:
ok all 1 test passed
Test #9:
score: 0
Accepted
time: 1ms
memory: 5824kb
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 3 4 4 5 5 6 6 7 8 9 9 10 13 14 16 17 18 19 1 3 6 8 9 11 9 12 9 13 13 15 13 16 16 18 18 20 1 5 1 8 1 13 1 18 23 1 2 2 3 5 6 7 8 10 11 11 12 15 16 16 17 18 19 19 20 2 4 2 5 5 7 7 9 7 10 11 13 11 14 11 15 16 18 1 7 1 11 1 16 1 19 23 2 3 4 5 6 7 11 12 12 13 14 15 16 17 17 18 18 19 1 3 1 4 4 6 6 8...
result:
ok all 4 test passed
Test #10:
score: 0
Accepted
time: 0ms
memory: 4100kb
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 4 5 5 6 9 10 11 12 12 13 15 16 16 17 20 21 23 24 25 26 27 28 28 29 30 31 31 32 32 33 34 35 37 38 38 39 39 40 40 41 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 53 54 54 55 57 58 60 61 61 62 64 65 67 68 68 69 69 70 70 71 71 72 73 74 74 75 76 77 78 79 79 80 83 84 85 86 86 87 87 88 89 90 91 ...
result:
ok all 4 test passed
Test #11:
score: 0
Accepted
time: 1ms
memory: 5880kb
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 4 5 7 8 9 10 10 11 13 14 15 16 16 17 19 20 21 22 23 24 25 26 28 29 29 30 30 31 32 33 33 34 35 36 37 38 38 39 39 40 41 42 42 43 43 44 45 46 46 47 50 51 51 52 52 53 53 54 54 55 56 57 57 58 62 63 65 66 67 68 68 69 69 70 73 74 75 76 78 79 80 81 83 84 84 85 86 87 87 88 88 89 89 90 90 91 91 92 94 ...
result:
ok all 1 test passed
Test #12:
score: 0
Accepted
time: 0ms
memory: 3812kb
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 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1 3 ...
result:
ok all 1 test passed
Test #13:
score: 0
Accepted
time: 0ms
memory: 3856kb
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 13 14 23 24 33 34 43 44 53 54 63 64 73 74 83 84 93 94 103 104 113 114 123 124 133 134 143 144 153 154 163 164 173 174 183 184 193 194 2 4 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 13 15 13 16 13 17 13 18 13 19 13 20 13 21 13 22 13 23 23 25 23 26 23 27 23 28 23 29 23 30 23 31 23 32 23 33 33...
result:
ok all 1 test passed
Test #14:
score: 0
Accepted
time: 0ms
memory: 3808kb
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 3 4 4 5 5 6 1 3 1 4 1 5 1 6 1 7 9 1 2 2 3 4 5 5 6 6 7 1 3 1 4 4 6 1 6 9 1 2 2 3 4 5 5 6 6 7 2 4 2 5 2 6 2 7 10 1 2 2 3 3 4 4 5 5 6 6 7 2 4 2 5 2 6 2 7
result:
ok all 4 test passed
Test #15:
score: -100
Wrong Answer
time: 1ms
memory: 5888kb
input:
4 20 3 1 2 3 1 3 2 1 1 2 3 1 2 2 1 1 2 2 1 2 2 20 3 1 2 1 2 3 3 2 1 1 3 3 2 2 1 2 3 1 1 2 2 20 3 3 1 1 3 3 1 3 2 1 1 2 3 3 3 1 1 2 1 1 1 20 3 3 2 2 1 3 1 1 3 3 2 2 2 1 1 2 1 2 2 2 2
output:
30 1 2 2 3 3 4 4 5 5 6 6 7 8 9 9 10 10 11 11 12 13 14 15 16 17 18 18 19 1 3 4 6 3 6 1 6 6 8 8 10 6 10 1 10 10 12 1 12 1 13 13 15 15 17 18 20 1 17 1 20 31 1 2 2 3 3 4 4 5 6 7 7 8 9 10 11 12 13 14 14 15 15 16 16 17 18 19 3 5 2 5 1 5 1 6 1 7 7 9 7 10 1 10 1 11 1 12 1 13 14 16 13 16 1 16 16 18 16 19 1 1...
result:
wrong answer output = 30, answer = 32.