68 lines
1.8 KiB
C++
68 lines
1.8 KiB
C++
|
#include <iostream>
|
||
|
|
#include <vector>
|
||
|
|
#include <queue>
|
||
|
|
|
||
|
|
using namespace std;
|
||
|
|
|
||
|
|
struct fruit {
|
||
|
|
int type;
|
||
|
|
int start;
|
||
|
|
int end;
|
||
|
|
|
||
|
|
fruit(int t, int start, int end) {
|
||
|
|
this->type = t;
|
||
|
|
this->start = start;
|
||
|
|
this->end = end;
|
||
|
|
}
|
||
|
|
};
|
||
|
|
|
||
|
|
bool took[200000 + 5], fruits[200000 + 5];
|
||
|
|
|
||
|
|
int main() {
|
||
|
|
int n;
|
||
|
|
queue<fruit> blocks, pending_blocks;
|
||
|
|
cin >> n;
|
||
|
|
for (int i = 1; i <= n; i++) {
|
||
|
|
cin >> fruits[i];
|
||
|
|
}
|
||
|
|
fruits[n + 1] = !fruits[n]; // Make the last block can be handled
|
||
|
|
for (int ptr = 2, lead = 1; ptr <= n + 1; ptr++) {
|
||
|
|
if (fruits[ptr] != fruits[ptr - 1]) {
|
||
|
|
blocks.emplace(fruits[ptr - 1], lead, ptr - 1);
|
||
|
|
lead = ptr;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
// 1st -> 1 1 0 0 1 1 1 0 1 1 0 0
|
||
|
|
// x x x x x x
|
||
|
|
// 2nd -> 1 0 1 1 0 0
|
||
|
|
int remain = n;
|
||
|
|
while (remain) {
|
||
|
|
while (!blocks.empty()) {
|
||
|
|
auto front = blocks.front();
|
||
|
|
blocks.pop();
|
||
|
|
while (took[front.start] && front.start <= front.end) front.start++;
|
||
|
|
if (front.start > front.end) continue;
|
||
|
|
printf("%d ", front.start);
|
||
|
|
remain--;
|
||
|
|
took[front.start] = true;
|
||
|
|
if (front.end == front.start) continue;
|
||
|
|
front.start++;
|
||
|
|
pending_blocks.push(front);
|
||
|
|
}
|
||
|
|
printf("\n");
|
||
|
|
while (!pending_blocks.empty()) {
|
||
|
|
auto front = pending_blocks.front();
|
||
|
|
pending_blocks.pop();
|
||
|
|
while (!pending_blocks.empty()) {
|
||
|
|
auto back = pending_blocks.front();
|
||
|
|
if (front.type == back.type) {
|
||
|
|
front.end = back.end;
|
||
|
|
pending_blocks.pop();
|
||
|
|
} else {
|
||
|
|
break;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
blocks.push(front);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|