cormoran's note


cormoran

競技プログラミング・電子工作・ロボットなどで遊びます



Recent Post




AOJ2152 Restrictive Filesystem

AOJ2152 Restrictive Filesystem

問題概要

0, 1, 2, 3, … と無限に記憶域を持つ記憶装置がある。

この装置に対し以下の3つの操作を行う

  • 書き込み

    記憶域をk$(0<=k<=10^9)$個必要とするデータを書き込む。データは記憶域の先頭から見て、まだ使われていない部分に順に入れられる。(つまり、断片化することもある)データには固有のidが与えられる。

  • 削除

    指定のidのデータを記憶域から削除する

  • 参照

    指定された番号の記憶域に書かれたデータのidを返す。

幾つかの操作指示が与えられるので、参照操作が与えられた時、上を満たすidを出力せよ。

解法

使用しうるセルの範囲が$10^9$と大きいのでそのまま配列を確保して愚直に..とはできない。

コマンド数が$N=10^4$なので各クエリの処理は$O(N)$くらいかかってもよく、記憶域を区間で持ってやれば良い。

記憶域はいつも前から見ていく上に、途中に挿入・削除をするので配列でなくlistを使うのがいい。


#include<iostream>
#include<vector>
#include<algorithm>
#include<list>
using namespace std;

#define rep(i, j) for(int i=0; i < (int)(j); i++)
#define repeat(i, j, k) for(int i = (j); i < (int)(k); i++)
#define all(v) v.begin(),v.end()
// vector
template<class T> istream& operator >> (istream &is , vector<T> &v) {
    for(T &a : v) is >> a; return is;
}

struct Packet {
    int id, pos, len;
};

bool solve() {
    int N; cin >> N;
    if(N == 0) return false;
    list<Packet> memory;
    rep(i, N) {
        char c; cin >> c;
        if(c == 'W') {
            int len, id; cin >> id >> len;
            int pos = 0;
            for(auto itr = memory.begin(); itr != memory.end(); itr++) {
                if(itr->pos > pos) {
                    int blank = itr->pos - pos;
                    Packet p = {id, pos, min(blank, len)};
                    memory.insert(itr, p);
                    len -= p.len;
                    if(len == 0) break;
                }
                pos = itr->pos + itr->len;
            }
            if(len > 0) {
                Packet p = {id, pos, len};
                memory.push_back(p);
            }
        } else if(c == 'D') {
            int id; cin >> id;
            for(auto itr = memory.begin(); itr != memory.end();) {
                if(itr->id == id) itr = memory.erase(itr);
                else itr++;
            }
        } else if(c == 'R') {
            int num; cin >> num;
            for(auto itr = memory.begin(); itr != memory.end(); itr++) {
                if(itr->pos <= num and num < itr->pos + itr->len){
                    cout << itr->id << endl;
                    goto END_R;
                }
            }
            cout << -1 << endl;
      END_R:;
        }
    }
    cout << endl;
    return true;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    while(solve());
    return 0;
}

comments powered by Disqus