社区讨论
现在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 条回复,欢迎继续交流。
正在加载回复...