社区讨论

现在vector常数这么大了吗?

P7912[CSP-J 2021] 小熊的果篮参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@m2hqrqf5
此快照首次捕获于
2024/10/20 23:27
去年
此快照最后确认于
2024/10/21 12:48
去年
查看原帖
代码模拟应该正确,预期复杂度O(n), 就稍稍用了一下vector然后全T了,跑了12s,n <= 5都没跑过,不理解。
CPP
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;
#define first fi
#define second se

inline ll read() {
	char c = getchar();
	ll sum = 0, flag = 1;
	while(c < '0' || c > '9') {if(c == '-') flag = -1; c = getchar(); }
	while(c >= '0' && c <= '9'){ sum = (sum << 1) + (sum << 3) + c - '0'; c = getchar(); }
	return sum * flag;
}
inline void write(ll x) {
	if(x < 0) x = (~x) + 1, putchar('-');
	if(x > 9) write(x / 10);
	putchar(x % 10 + '0'); 
}

const int MAXN = 2e5 + 5;

int n, tot, tmp;
bool x;
struct node {
	bool flag;//当前块为苹果还是橘子
	int lst, nxt;//该块的下一个块
	vector<int> block;
} a[MAXN];

void init() {
	tmp = !tmp;
	a[tot].lst = tot - 1, a[tot].nxt = ++tot;
	a[tot].flag = tmp;
	return ;
}
void merge(int k) {
	if(a[k].lst == 0) {
		a[0].nxt = a[k].nxt;
		a[a[k].nxt].lst = 0;
	}
	else if(a[k].nxt == -1) {
		a[a[k].lst].nxt = -1;
	}
	else {
		int u = a[k].lst, v = a[k].nxt;
		for(auto i : a[v].block) {
			a[u].block.emplace_back(i);
		}
		a[u].nxt = a[v].nxt;
		if(a[v].nxt != -1) {
			a[a[v].nxt].lst = u;
		}
	}
	return ;
}

int main() {
	n = read(), x = read();
	tmp = !x, init();
	a[tot].block.emplace_back(1);
	for(int i = 2; i <= n; ++i) {
		x = read();
		if(tmp != x) {
			init();
		}
		a[tot].block.emplace_back(i);
	}
	a[tot].lst = tot - 1, a[tot].nxt = -1;
//	for(int i = 0; i <= tot; ++i) {
//		cout << i << ':' << '\n';
//		cout << a[i].flag << ' ' << a[i].lst << ' ' << a[i].nxt << '\n';
//		for(auto j : a[i].block) {
//			cout << j << ' ';
//		}
//		cout << '\n';
//	}
	while(1) {
		if(a[0].nxt == -1) {
			break;
		}
		for(int i = a[0].nxt; i != -1; i = a[i].nxt) {
			if(a[i].block.size()) {
				write(a[i].block[0]), putchar(' ');
				a[i].block.erase(a[i].block.begin());
			}
		}
		for(int i = a[0].nxt; i != -1; i = a[i].nxt) {
			if(!a[i].block.size()) {
				merge(i);
			}
		}
		putchar('\n');
	}
	return 0;
}

回复

2 条回复,欢迎继续交流。

正在加载回复...