Algoogle

Algorithm for Programming Contest

AOJ 2152 Restrictive Filesystem

Category: AOJ Tag: implementation

Restrictive Filesystem

問題概要


解法


区間を長さで区切っていく感じでやる.
各識別番号は1~10010に順に割り当てる.
割り当てられた番号は削除済みかどうかの情報を持つ.
書き込むときは削除済みの場所に小さいところから書き込む.
削除された区間の途中で書き込むのが終わるなら、そこで区切る(区間が増える).
初期状態は削除済みの長い区間を持つ.
読むときは区間を順にみていけばよい.
削除するときはその識別番号を削除済みにすればよい.

コード


(2152.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>

#define repi(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,a) repi(i,0,a)
#define pb push_back
#define fst first
#define snd second
#define INF 1e9

using namespace std;

typedef vector<int> vi;
typedef pair<int,int> pii;

int n;
map<int,int> id;
bool deleted[10010];
vector<pii> data;
const int M = 10005;

void init(){
    id.clear();
    memset(deleted, 0, sizeof(deleted));
    id[M] = 0;
    deleted[0] = true;
    data.clear();
    data.pb(pii(M,INF+10));
}

void write(int cnt){
    int l, s; cin >> l >> s;
    id[l] = cnt;
    rep(i,data.size()){
        if(deleted[id[data[i].fst]]){
            if(data[i].snd <= s){
                data[i].fst = l;
                s -= data[i].snd;
            }
            else{
                data.insert(data.begin()+i+1,pii(M,data[i].snd - s));
                data[i].fst = l;
                data[i].snd = s;
                s = 0;
            }
            if(!s) return;
        }
    }
    return;
}

int read(){
    int p; cin >> p;
    p++;
    rep(i,data.size()){
        if(p > data[i].snd) p -= data[i].snd;
        else if(deleted[id[data[i].fst]]) return -1;
        else return data[i].fst;
    }
    return -1;
}

void del(){
    int l; cin >> l;
    l = id[l];
    deleted[l] = true;
}

int main(){
    while(cin >> n, n){
        int cnt = 0;
        init();
        while(n--){
            char com; cin >> com;
            if(com == 'W') write(++cnt);
            if(com == 'R') cout << read() << endl;
            if(com == 'D') del();
        }
        cout << endl;
    }
    return 0;
}

Comments