QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#425042 | #6537. One, Two, Three | DaiRuiChen007 | WA | 0ms | 32604kb | C++14 | 1.1kb | 2024-05-29 21:39:47 | 2024-05-29 21:39:49 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int MAXN=6e5+5;
int A[MAXN],B[MAXN],C[MAXN],z[MAXN];
vector <int> f[4],o1[MAXN],o2[MAXN];
signed main() {
int n;
scanf("%d",&n);
for(int i=1;i<=n;++i) {
scanf("%d",&z[i]),f[z[i]].push_back(i);
A[i]=A[i-1]+(z[i]==1);
B[i]=B[i-1]+(z[i]==2);
C[i]=C[i-1]+(z[i]==3);
}
int S=n,T=n,R=min(A[n],C[n]);
for(int i=1,s=0,t=0,r=0;i<=n;++i) {
R=min(R,A[n]-A[i]+C[n]-C[i]+B[i]+r);
r=min(r,A[i]+C[i]-B[i]);
S=min(S,C[n]-C[i]+B[i]+s);
s=min(s,A[i]-B[i]);
T=min(T,A[n]-A[i]+B[i]+t);
t=min(t,C[i]-B[i]);
}
R=min(R,S+T),T=R-S;
if(T<0) S-=T,T=0;
printf("%d\n",R);
for(int i=0;i<S;++i) o1[f[1][i]].push_back(f[3][C[n]-S+i]);
for(int i=0;i<T;++i) o2[f[3][i]].push_back(f[1][A[n]-T+i]);
deque <array<int,2>> q1,q2;
for(int i=1;i<=n;++i) {
for(int x:o1[i]) q1.push_back({x,i});
for(int x:o2[i]) q2.push_back({x,i});
if(z[i]==2&&(q1.size()||q2.size())) {
array<int,2> w;
if(q2.empty()||q1[0]<q2[0]) w=q1[0],q1.pop_front();
else w=q2[0],q2.pop_front();
printf("%d %d %d\n",w[1]-1,i-1,w[0]-1);
}
}
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 32604kb
input:
6 3 1 2 2 3 1
output:
2 1 2 4 -1 3 -1
result:
wrong answer invalid triple