灵异错误
  • 板块学术版
  • 楼主zlttcl
  • 当前回复4
  • 已保存回复4
  • 发布时间2023/10/17 20:15
  • 上次更新2023/11/2 13:12:50
查看原帖
灵异错误
555381
zlttcl楼主2023/10/17 20:15

交上去全错,错误信息全是第一行第一个数输出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;
}
2023/10/17 20:15
加载中...