交上去全错,错误信息全是第一行第一个数输出0,但是下载测试数据后本地是对的。
Code:
//#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
ll n, fa[N], a[N], b[N], sum, cnt, cnt2, ttt, t[N], h[N], h2[N];
inline ll read(){
ll x = 0, m = 1;
char ch = getchar();
while(!isdigit(ch)){
if(ch == '-') m = -1;
ch = getchar();
}
while(isdigit(ch)){
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * m;
}
inline void write(ll x){
if(x < 0){
putchar('-');
write(-x);
return;
}
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
inline int find(int x){
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
inline void merge(int x, int y){
int u = find(x), v = find(y);
if(u > v) swap(u, v);
fa[u] = v;
}
signed main(){
//freopen(".in", "r", stdin);
//freopen(".out", "w", stdout);
n = read();
for(int i = 1; i <= n; ++ i) fa[i] = i;
for(int i = 1; i <= n; ++ i) a[i] = read();
b[++ cnt] = h[cnt] = 1;
for(int i = 2; i <= n; ++ i){
if(a[i] != a[i - 1]) h[++ cnt] = i;
++ b[cnt];
}
while(sum < n){
for(int i = 1; i < cnt; ++ i) write(h[i]), putchar(' '), merge(h[i] - 1, h[i]);
write(h[cnt]), putchar('\n');
sum += cnt;
merge(h[cnt] - 1, h[cnt]);
cnt2 = ttt = 0;
for(int i = 1; i <= cnt; ++ i){
if(b[i] > 1){
if(ttt % 2 == 0 || !cnt2 || b[i - 1] > 1) h2[++ cnt2] = find(h[i]) + 1, t[cnt2] = 0;
t[cnt2] += (b[i] - 1);
ttt = 0;
}else ++ ttt;
}
cnt = cnt2;
for(int i = 1; i <= cnt; ++ i) b[i] = t[i], h[i] = h2[i];
}
return 0;
}