AOJ 2152 : Restrictive Filesystem
問題リンク:Restrictive Filesystem | Aizu Online Judge
解法:
双方向連結リストを実装した
コード:
const uint64_t INF = 100000000000010; struct List { int identifier; uint64_t range[2];// [range[0],range[1]] bool hasNext,hasPrev; List *prev; List *next; List(int identifier=inf,uint64_t r1=INF,uint64_t r2=INF):identifier(identifier) { range[0] = r1, range[1] = r2; hasNext = hasPrev = false; } }; int N,I,S,P; char c; List list; void list_walk(List *l) { cout << '[' << l->range[0] << "," << l->range[1] << " : " << l->identifier << "]"; if(l->hasNext)list_walk(l->next); } void ddfs(List *l) { if(l->hasNext)ddfs(l->next); if(l->hasPrev)delete l; } void init() { if(list.hasNext)ddfs(&list); list.hasNext = true; list.hasPrev = false; list.range[0] = list.range[1] = -1; list.identifier = -1; list.next = new List; list.next->hasNext = false; list.next->hasPrev = true; list.next->range[0] = list.next->range[1] = INF; list.next->identifier = inf; list.next->prev = &list; } void dfsW(List *l) { uint64_t v1 = l->range[1]; uint64_t v2 = l->next->range[0]; uint64_t diff = v2-v1-1; if(diff) { List *node = new List; node->identifier = I; node->hasNext = node->hasPrev = true; node->next = l->next; node->prev = l; l->next->prev = node; l->next = node; node->range[0] = v1+1; if(S <= diff) { node->range[1] = node->range[0] + S - 1; S = 0; } else if(S > diff) { node->range[1] = node->range[0] + diff - 1; S -= diff; } } if(S > 0)dfsW(l->next); } void compute_W() { dfsW(&list); } void dfsD(List *l) { if(l->identifier == I) { l->next->prev = l->prev; l->prev->next = l->next; delete l; } if(l->hasNext)dfsD(l->next); } void compute_D() { dfsD(&list); } void dfsR(List *l) { if(l->range[0] <= P && P <= l->range[1]) { cout << l->identifier << endl; } else { if(l->hasNext)dfsR(l->next); else cout << -1 << endl; } } void compute_R() { dfsR(&list); } int main() { while(cin >> N,N) { init(); rep(_,N) { cin >> c; if(c == 'W')cin >> I >> S,compute_W(); if(c == 'D')cin >> I,compute_D(); if(c == 'R')cin >> P,compute_R(); } cout << endl; } return 0; }