7BUnreviewed1600GPT-5.4 (high)

Memory Manager

Progressive hints first, then the full explanation and implementation when you're ready to cash out.

implementation

Original problem

Review status

AI-generated and still unreviewed. Double-check the details before internalizing them.

Hints

Progressive nudges

Open only as much as you need to keep the solve alive.

The constraints are tiny: $t,m \le 100$ . So don't invent some cursed interval tree. A direct simulation is totally fine.

Represent memory literally: an array of length $m$ , where each byte stores either $0$ for free or the block id that currently owns it.

For alloc n, scan from left to right and find the first run of $n$ consecutive zeroes. That gives the leftmost valid place automatically.

For erase x, you need to know whether $x$ is a currently alive block id. Keep an alive[id] array. If x is invalid or already erased, print ILLEGAL_ERASE_ARGUMENT; otherwise clear every cell equal to $x$ .

defragment is just stable compaction of the memory array: move every nonzero cell to the front, preserving order, then fill the rest with zeroes. Since each block is always a contiguous run of equal ids, deleting the gaps keeps block order and block contiguity intact.

Key observation

This is pure simulation. Full stop. With $t,m \le 100$ , anything asymptotically fancy is just showing off to the wall.

So we model the memory exactly as it is described.

Let mem[i] denote byte $i$ of memory:

0 if the byte is free,
the block id otherwise.

Also keep:

alive[id] — whether this identifier currently refers to a live block,
nextId — the next identifier to give to a successful alloc.

That is enough.

`alloc n`

We need the leftmost free segment of length $n$ .

A left-to-right scan with a running count of consecutive free bytes does the job:

if mem[i] == 0, increase the current free-run length,
otherwise reset it to $0$ .

The first time the run length becomes $n$ , we found the earliest valid segment. Its start is

start = i - n + 1.

If no such segment exists, print NULL.

Otherwise:

fill mem[start ... start+n-1] with nextId,
mark alive[nextId] = true,
print nextId,
increment nextId.

And yeah, unsuccessful allocations do not increment the id counter. That little detail is where people randomly trip and eat dirt.

`erase x`

An erase is legal iff $x$ is the id of a currently alive block.

So it is illegal when

x \le 0 \quad \text{or} \quad x \ge \text{nextId} \quad \text{or} \quad \neg alive[x].

In that case, print ILLEGAL_ERASE_ARGUMENT.

Otherwise:

set alive[x] = false,
scan the whole memory and replace every occurrence of $x$ with $0$ .

Because each live block occupies one contiguous segment, this removes exactly that block.

`defragment`

After defragmentation, all occupied bytes must be moved as far left as possible, while preserving the order of blocks.

The easiest way to think about it: just remove all zeroes from the memory array and keep the nonzero values in the same order.

Example:

[1,1,0,2,2,2,0,3] \rightarrow [1,1,2,2,2,3,0,0].

An in-place stable compaction does exactly this:

keep a write pointer w = 0,
scan i = 0..m-1,
whenever mem[i] != 0, write mem[w++] = mem[i],
after the scan, fill mem[w ... m-1] with 0.

Why does this preserve block structure?

Because before defragmentation, memory is a sequence of contiguous block-runs separated by zero-runs. Removing all zero-runs simply concatenates the block-runs in the same order. No block gets reordered, and no block gets split. Nice and clean.

Correctness sketch

We maintain this invariant after every operation:

each live block id appears in mem as one contiguous segment,
alive[id] is true iff that block exists and has not been erased,
free bytes are exactly the positions where mem[i] = 0.

Now check the operations:

alloc writes one new contiguous segment into the leftmost valid gap,
erase removes exactly one existing segment,
defragment deletes all gaps while preserving the order of occupied bytes.

So every operation matches the statement exactly.

Complexity

Each command scans at most $m$ bytes, so each one costs $O(m)$ . Hence total complexity is

O(t \cdot m).

Given $t,m \le 100$ , this is at most

O(10^4),

which is hilariously small.

Memory usage is $O(m + t)$ .

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

int main() {
    setIO();

    int t, m;
    cin >> t >> m;

    vector<int> mem(m, 0);          // 0 = free, otherwise block id
    vector<int> alive(t + 5, 0);    // ids are at most number of successful allocs <= t
    int nextId = 1;

    for (int q = 0; q < t; q++) {
        string op;
        cin >> op;

        if (op == "alloc") {
            int n;
            cin >> n;

            int run = 0, start = -1;
            for (int i = 0; i < m; i++) {
                if (mem[i] == 0) run++;
                else run = 0;

                if (run == n) {
                    start = i - n + 1;
                    break;
                }
            }

            if (start == -1) {
                cout << "NULL\n";
            } else {
                for (int i = start; i < start + n; i++) mem[i] = nextId;
                alive[nextId] = 1;
                cout << nextId << '\n';
                nextId++;
            }
        } else if (op == "erase") {
            ll x;
            cin >> x;

            if (x <= 0 || x >= nextId || !alive[(int)x]) {
                cout << "ILLEGAL_ERASE_ARGUMENT\n";
            } else {
                alive[(int)x] = 0;
                for (int i = 0; i < m; i++) {
                    if (mem[i] == x) mem[i] = 0;
                }
            }
        } else { // defragment
            int w = 0;
            for (int i = 0; i < m; i++) {
                if (mem[i] != 0) mem[w++] = mem[i];
            }
            while (w < m) mem[w++] = 0;
        }
    }

    return 0;
}

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

int main() {
    setIO();

    int t, m;
    cin >> t >> m;

    vector<int> mem(m, 0);          // 0 = free, otherwise block id
    vector<int> alive(t + 5, 0);    // ids are at most number of successful allocs <= t
    int nextId = 1;

    for (int q = 0; q < t; q++) {
        string op;
        cin >> op;

        if (op == "alloc") {
            int n;
            cin >> n;

            int run = 0, start = -1;
            for (int i = 0; i < m; i++) {
                if (mem[i] == 0) run++;
                else run = 0;

                if (run == n) {
                    start = i - n + 1;
                    break;
                }
            }

            if (start == -1) {
                cout << "NULL\n";
            } else {
                for (int i = start; i < start + n; i++) mem[i] = nextId;
                alive[nextId] = 1;
                cout << nextId << '\n';
                nextId++;
            }
        } else if (op == "erase") {
            ll x;
            cin >> x;

            if (x <= 0 || x >= nextId || !alive[(int)x]) {
                cout << "ILLEGAL_ERASE_ARGUMENT\n";
            } else {
                alive[(int)x] = 0;
                for (int i = 0; i < m; i++) {
                    if (mem[i] == x) mem[i] = 0;
                }
            }
        } else { // defragment
            int w = 0;
            for (int i = 0; i < m; i++) {
                if (mem[i] != 0) mem[w++] = mem[i];
            }
            while (w < m) mem[w++] = 0;
        }
    }

    return 0;
}

View on Codeforces Back to the list