70pts TLE,TLEon#6#8#9
查看原帖
70pts TLE,TLEon#6#8#9
762086
Francium_楼主2024/6/5 18:02
#include <bits/stdc++.h>
using namespace std;
const int N = 2 * 1e5;

struct fruit {
	int number;
	int aoro;
};
int ne[N], f[N], head = 1, n;
fruit e[N];
bool flag[N];

int read() {
	int x = 0;
	bool flag = false;
	char ch = getchar();
	while (!isdigit(ch))
		flag = ch == '-', ch = getchar();
	while (isdigit(ch))
		x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
	flag ? x = -x : 0;
	return x;
}

void write(int x) {
	if (x > 9)
		write(x / 10);
	putchar(x % 10 + '0');
}

void Detele(int x) {
	if (x == head) {
		f[ne[head]] = -1;
		head = ne[head];
	} else if (ne[x] == n + 1) {
		ne[f[x]] = n + 1;
	} else {
		ne[f[x]] = ne[x];
		f[ne[x]] = f[x];
	}
}

int main() {
	//ios::sync_with_stdio(false);
	//cout.tie(0);
	bool c;
	bool flag1 = 1;
	n = read();
	for (int i = 1; i <= n; i++) {
		e[i].aoro = read();
		if (i == 1)
			c = e[i].aoro;
		if (e[i].aoro != c)
			flag1 = 0;
		e[i].number = i;
		ne[i] = i + 1;
		f[i] = i - 1;
	}
	ne[n + 1] = -1;
	e[n + 1].aoro = 34;
	f[1] = -1;
	if (flag1) {
		for (int i = 1; i <= n; i++) {
			write(i);
			cout << '\n';
		}
		return 0;
	}
	while (1) {
		vector<int>ans;
		memset(flag, 0, sizeof(flag));
		for (int i = head; ne[i] != -1; i = ne[i]) {
			if (flag[i])
				continue;
			ans.push_back(i);
			for (int j = i; e[i].aoro == e[j].aoro; j = ne[j]) {
				flag[j] = true;
			}
			Detele(i);
		}
		for (int i = 0; i < ans.size(); i++) {
			write(ans[i]);
			cout << " ";
		}
		cout << '\n';
		if (ne[head] == -1)
			break;
	}
	return 0;
}
2024/6/5 18:02
加载中...