HDOJ 5071 Chat 模擬

大模擬：

1》saygoodbye要先對 always on top 的人說
2》對沒有說過話的不要說good bye
3》用long long

Chat

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 337 Accepted Submission(s): 82


Problem Description As everyone knows, DRD has no girlfriends. But as everyone also knows, DRD’s friend ATM’s friend CLJ has many potential girlfriends. One evidence is CLJ’s chatting record.


CLJ chats with many girls all the time. Sometimes he begins a new conversation and sometimes he ends a conversation. Sometimes he chats with the girl whZ喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vc2Ugd2luZG93IGlzIG9uIHRoZSB0b3AuPGJyPgo8YnI+CllvdSBjYW4gaW1hZ2luZSBDTEqhr3Mgd2luZG93cyBhcyBhIHF1ZXVlLiBUaGUgZmlyc3QgZ2lybCBpbiB0aGUgcXVldWUgaXMgdGhlIHRvcCBnaXJsIGlmIG5vIG9uZSBpcyChsGFsd2F5cyBvbiB0b3AgobEuPGJyPgo8YnI+ClNpbmNlIENMSiBpcyBzbyBwb3B1bGFyLCBoZSBiZWdpbnMgdG8gYXNzaWduIGEgdW5pcXVlIHBvc2l0aXZlIGludGVnZXIgYXMgcHJpb3JpdHkgZm9yIGV2ZXJ5IGdpcmwuIFRoZSBoaWdoZXIgcHJpb3JpdHkgYSBnaXJsIGhhcywgdGhlIG1vcmUgQ0xKIGxpa2VzIGhlci4gRm9yIGV4YW1wbGUsIEdZWiBoYXMgcHJpb3JpdHkgMTA8c3VwPjk8L3N1cD4sIGFuZCBKWlAgaGFzIHByaW9yaXR5IDEwPHN1cD44PC9zdXA+IHdoaWxlIFNpc3RlciBTb3VwIGhhcwogcHJpb3JpdHkgMSwgYW5kIEZhY2UgRmFjZSBoYXMgcHJpb3JpdHkgMi48YnI+Cjxicj4KQXMgYSBmYW1vdXMgcHJvZ3JhbW1lciwgQ0xKIGxlYWRzIGEgZ3JvdXAgdG8gaW1wbGVtZW50IGhpcyBvd24gV00od2luZG93IG1hbmFnZXIpLiBUaGUgV00gd2lsbCBsb2cgQ0xKoa9zIG9wZXJhdGlvbnMuIE5vdyB5b3UgYXJlIHN1cHBvc2VkIHRvIGltcGxlbWVudCB0aGUgbG9nIHN5c3RlbS4gVGhlIGdlbmVyYWwgbG9nZ2luZyBmb3JtYXQgaXMgobBPcGVyYXRpb24gI1g6IExPR01TRy6hsSwgd2hlcmUgWCBpcyB0aGUgbnVtYmVyIG9mIHRoZSBvcGVyYXRpb24KIGFuZCBMT0dNU0cgaXMgdGhlIGxvZ2dpbmcgbWVzc2FnZS48YnI+Cjxicj4KVGhlcmUgYXJlIHNldmVyYWwga2luZHMgb2Ygb3BlcmF0aW9ucyBDTEogbWF5IHVzZTo8YnI+Cjxicj4KMS48c3Ryb25nPkFkZCB1Ojwvc3Ryb25nPiBDTEogb3BlbnMgYSBuZXcgd2luZG93IHdob3NlIHByaW9yaXR5IGlzIHUsIGFuZCB0aGUgbmV3IHdpbmRvdyB3aWxsIGJlIHRoZSBsYXN0IHdpbmRvdyBpbiB0aGUgd2luZG93IHF1ZXVlLiBUaGlzIG9wZXJhdGlvbiB3aWxsIGFsd2F5cyBiZSBzdWNjZXNzZnVsIGV4Y2VwdCB0aGUgb25seSBjYXNlIGluIHdoaWNoIHRoZXJlIGlzIGFscmVhZHkgYSB3aW5kb3cgd2l0aCBwcmlvcml0eSB1LiBJZiBpdCBpcwogc3VjY2Vzc2Z1bCwgTE9HTVNHIHdpbGwgYmUgobBzdWNjZXNzobEuIE90aGVyd2lzZSBMT0dNU0cgd2lsbCBiZSChsHNhbWUgcHJpb3JpdHmhsS48YnI+Cjxicj4KMi48c3Ryb25nPkNsb3NlIHU6PC9zdHJvbmc+IENMSiBjbG9zZXMgYSB3aW5kb3cgd2hvc2UgcHJpb3JpdHkgaXMgdS4gSWYgdGhlcmUgZXhpc3RzIHN1Y2ggYSB3aW5kb3csIHRoZSBvcGVyYXRpb24gd2lsbCBiZSBzdWNjZXNzZnVsIGFuZCBMT0dNU0cgd2lsbCBiZSChsGNsb3NlIHUgd2l0aCBjobEsIHdoZXJlIHUgaXMgdGhlIHByaW9yaXR5IGFuZCBjIGlzIHRoZSBudW1iZXIgb2Ygd29yZHMgQ0xKIGhhcyBzcG9rZW4gdG8gdGhpcyB3aW5kb3cuIE90aGVyd2lzZSwKIExPR01TRyB3aWxsIGJlIKGwaW52YWxpZCBwcmlvcml0eaGxLiBOb3RlIHRoYXQgQU5ZIHdpbmRvdyBjYW4gYmUgY2xvc2VkLjxicj4KPGJyPgozLjxzdHJvbmc+Q2hhdCB3Ojwvc3Ryb25nPiBDTEogY2hhdHMgd2l0aCB0aGUgdG9wIHdpbmRvdywgYW5kIGhlIHNwZWFrcyB3IHdvcmRzLiBUaGUgdG9wIHdpbmRvdyBpcyB0aGUgZmlyc3Qgd2luZG93IGluIHRoZSBxdWV1ZSwgb3IgdGhlIKGwYWx3YXlzIG9uIHRvcKGxIHdpbmRvdyAoYXMgZGVzY3JpYmVkIGJlbG93KSBpbnN0ZWFkIGlmIHRoZXJlIGV4aXN0cy4gSWYgbm8gd2luZG93IGlzIGluIHRoZSBxdWV1ZSwgTE9HTVNHIHdpbGwgYmUgobBlbXB0eaGxLAogb3RoZXJ3aXNlIHRoZSBvcGVyYXRpb24gY2FuIGJlIHN1Y2Nlc3NmdWwgYW5kIExPR01TRyB3aWxsIGJlIKGwc3VjY2Vzc6GxLjxicj4KPGJyPgo0LjxzdHJvbmc+Um90YXRlIHg6PC9zdHJvbmc+IENMSiBwZXJmb3JtcyBvbmUgb3IgbW9yZSBBbHQtVGFicyB0byBtb3ZlIHRoZSB4LXRoIHdpbmRvdyB0byB0aGUgZmlyc3Qgb25lIGluIHRoZSBxdWV1ZS4gRm9yIGV4YW1wbGUsIGlmIHRoZXJlIGFyZSA0IHdpbmRvd3MgaW4gdGhlIHF1ZXVlLCB3aG9zZSBwcmlvcml0aWVzIGFyZSAxLCAzLCA1LCA3IHJlc3BlY3RpdmVseSBhbmQgQ0xKIHBlcmZvcm1zIKGwUm90YXRlIDOhsSwgdGhlbiB0aGUgd2luZG93oa9zCiBwcmlvcml0aWVzIGluIHRoZSBxdWV1ZSB3aWxsIGJlY29tZSA1LCAxLCAzLCA3LiBOb3RlIHRoYXQgaWYgQ0xKIHdhbnRzIHRvIG1vdmUgdGhlIGZpcnN0IHdpbmRvdyB0byB0aGUgaGVhZCwgdGhpcyBvcGVyYXRpb24gaXMgc3RpbGwgY29uc2lkZXJlZCChsHN1Y2Nlc3NmdWyhsS4gSWYgeCBpcyBvdXQgb2YgcmFuZ2UgKHNtYWxsZXIgdGhhbiAxIG9yIGxhcmdlciB0aGFuIHRoZSBzaXplIG9mIHRoZSBxdWV1ZSksIExPR01TRyB3aWxsIGJlIKGwb3V0IG9mCiByYW5nZaGxLiBPdGhlcndpc2UgTE9HTVNHIHNob3VsZCBiZSChsHN1Y2Nlc3OhsS48YnI+Cjxicj4KNS48c3Ryb25nPlByaW9yOjwvc3Ryb25nPiBDTEogZmluZHMgb3V0IHRoZSBnaXJsIHdpdGggdGhlIG1heGltdW0gcHJpb3JpdHkgYW5kIHRoZW4gbW92ZXMgdGhlIHdpbmRvdyB0byB0aGUgaGVhZCBvZiB0aGUgcXVldWUuIE5vdGUgdGhhdCBpZiB0aGUgZ2lybCB3aXRoIHRoZSBtYXhpbXVtIHByaW9yaXR5IGlzIGFscmVhZHkgdGhlIGZpcnN0IHdpbmRvdywgdGhpcyBvcGVyYXRpb24gaXMgY29uc2lkZXJlZCBzdWNjZXNzZnVsIGFzIHdlbGwuIElmIHRoZQogd2luZG93IHF1ZXVlIGlzIGVtcHR5LCB0aGlzIG9wZXJhdGlvbiB3aWxsIGZhaWwgYW5kIExPR01TRyBtdXN0IGJlIKGwZW1wdHmhsS4gSWYgaXQgaXMgc3VjY2Vzc2Z1bCwgTE9HTVNHIG11c3QgYmUgobBzdWNjZXNzobEuPGJyPgo8YnI+CjYuPHN0cm9uZz5DaG9vc2UgdTo8L3N0cm9uZz4gQ0xKIGNob29zZXMgdGhlIGdpcmwgd2l0aCBwcmlvcml0eSB1IGFuZCBtb3ZlcyB0aGUgd2luZG93IHRvIHRoZSBoZWFkIG9mIHRoZSBxdWV1ZS5UaGlzIG9wZXJhdGlvbiBpcyBjb25zaWRlcmVkIHN1Y2Nlc3NmdWwgaWYgYW5kIG9ubHkgaWYgdGhlIHdpbmRvdyB3aXRoIHByaW9yaXR5IHUgZXhpc3RzLiBMT0dNU0cgZm9yIHRoZSBzdWNjZXNzZnVsIGNhc2VzIHNob3VsZCBiZSChsHN1Y2Nlc3OhsSBhbmQKIGZvciB0aGUgb3RoZXIgY2FzZXMgc2hvdWxkIGJlIKGwaW52YWxpZCBwcmlvcml0eaGxLjxicj4KPGJyPgo3LjxzdHJvbmc+VG9wIHU6PC9zdHJvbmc+IENMSiBtYWtlcyB0aGUgd2luZG93IG9mIHRoZSBnaXJsIHdpdGggcHJpb3JpdHkgdSBhbHdheXMgb24gdG9wLiBBbHdheXMgb24gdG9wIGlzIGEgc3BlY2lhbCBzdGF0ZSwgd2hpY2ggbWVhbnMgd2hvZXZlciB0aGUgZmlyc3QgZ2lybCBpbiB0aGUgcXVldWUgaXMsIHRoZSB0b3Agb25lIG11c3QgYmUgdSBpZiB1IGlzIGFsd2F5cyBvbiB0b3AuIEFzIHlvdSBjYW4gc2VlLCB0d28gZ2lybHMgY2Fubm90IGJlCiBhbHdheXMgb24gdG9wIGF0IHRoZSBzYW1lIHRpbWUsIHNvIGlmIG9uZSBnaXJsIGlzIGFsd2F5cyBvbiB0b3Agd2hpbGUgQ0xKIHdhbnRzIGFub3RoZXIgYWx3YXlzIG9uIHRvcCwgdGhlIGZpcnN0IHdpbGwgYmUgbm90IGFsd2F5cyBvbiB0b3AgYW55IG1vcmUsIGV4Y2VwdCB0aGUgdHdvIGdpcmxzIGFyZSB0aGUgc2FtZSBvbmUuIEFueW9uZSBjYW4gYmUgYWx3YXlzIG9uIHRvcC4gTE9HTVNHIGlzIHRoZSBzYW1lIGFzIHRoYXQgb2YgdGhlIENob29zZQogb3BlcmF0aW9uLjxicj4KPGJyPgo4LjxzdHJvbmc+VW50b3A6PC9zdHJvbmc+IENMSiBjYW5jZWxzIHRoZSChsGFsd2F5cyBvbiB0b3ChsSBzdGF0ZSBvZiB0aGUgZ2lybCB3aG8gaXMgYWx3YXlzIG9uIHRvcC4gVGhhdCBpcywgdGhlIGdpcmwgd2hvIGlzIGFsd2F5cyBvbiB0b3Agbm93IGlzIG5vdCBpbiB0aGlzIHNwZWNpYWwgc3RhdGUgYW55IG1vcmUuIFRoaXMgb3BlcmF0aW9uIHdpbGwgZmFpbCB1bmxlc3MgdGhlcmUgaXMgb25lIGdpcmwgYWx3YXlzIG9uIHRvcC4gSWYgaXQgZmFpbHMsCiBMT0dNU0cgc2hvdWxkIGJlIKGwbm8gc3VjaCBwZXJzb26hsSwgb3RoZXJ3aXNlIHNob3VsZCBiZSChsHN1Y2Nlc3OhsS48YnI+Cjxicj4KQXMgYSBnZW50bGVtYW4sIENMSiB3aWxsIHNheSBnb29kYnllIHRvIGV2ZXJ5IGFjdGl2ZSB3aW5kb3cgaGUgaGFzIGV2ZXIgc3Bva2VuIHRvIGF0IGxhc3QsIKGwYWN0aXZlobEgaGVyZSBtZWFucyB0aGUgd2luZG93IGhhcyBub3QgYmVlbiBjbG9zZWQgc28gZmFyLiBUaGUgbG9nZ2luZyBmb3JtYXQgaXMgobBCeWUgdTogY6GxIHdoZXJlIHUgaXMgdGhlIHByaW9yaXR5IGFuZCBjIGlzIHRoZSBudW1iZXIgb2Ygd29yZHMgaGUgaGFzIGV2ZXIgc3Bva2VuIHRvCiB0aGlzIHdpbmRvdy4gSGUgd2lsbCBhbHdheXMgc2F5IGdvb2QgYnllIHRvIHRoZSBjdXJyZW50IHRvcCBnaXJsIGlmIGhlIGhhcyBzcG9rZW4gdG8gaGVyIGJlZm9yZSBoZSBjbG9zZXMgaXQuCgogCjxicj4KCklucHV0CgpUaGUgZmlyc3QgbGluZSBjb250YWlucyBhbiBpbnRlZ2VyIFQgKFQgodwgMTApLCBkZW5vdGluZyB0aGUgbnVtYmVyIG9mIHRoZSB0ZXN0IGNhc2VzLjxicj4KPGJyPgpGb3IgZWFjaCB0ZXN0IGNhc2UsIHRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIGFuIGludGVnZXIgbigwIDwgbiCh3CA1MDAwKSwgcmVwcmVzZW50aW5nIHRoZSBudW1iZXIgb2Ygb3BlcmF0aW9ucy4gVGhlbiBmb2xsb3cgbiBvcGVyYXRpb25zLCBvbmUgaW4gYSBsaW5lLiBBbGwgdGhlIHBhcmFtZXRlcnMgYXJlIHBvc2l0aXZlIGludGVnZXJzIGJlbG93IDEwPHN1cD45PC9zdXA+LgoKIAo8YnI+CgpPdXRwdXQKCk91dHB1dCBhbGwgdGhlIGxvZ2dpbmcgY29udGVudHMuCgogCjxicj4KClNhbXBsZSBJbnB1dAoKPHByZSBjbGFzcz0="brush:java;">1 18 Prior Add 1 Chat 1 Add 2 Chat 2 Top 2 Chat 3 Untop Chat 4 Choose 2 Chat 5 Rotate 2 Chat 4 Close 2 Add 3 Prior Chat 2 Close 1
Sample Output

Operation #1: empty.
Operation #2: success.
Operation #3: success.
Operation #4: success.
Operation #5: success.
Operation #6: success.
Operation #7: success.
Operation #8: success.
Operation #9: success.
Operation #10: success.
Operation #11: success.
Operation #12: success.
Operation #13: success.
Operation #14: close 2 with 8.
Operation #15: success.
Operation #16: success.
Operation #17: success.
Operation #18: close 1 with 11.
Bye 3: 2

HintThis problem description does not relate to any real person in THU. 

Source 2014 Asia AnShan Regional Contest

#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long int LL;

const int INF=0x3f3f3f3f;

const int HEAD=0;
const int TAIL=6400;

struct CHART
{
    int pro,front,back;
    LL w;
}chat[6500];

int n,x,id;
int alwayson;
set pc;
char cmd[50];

void init()
{
    id=1;pc.clear();alwayson=-1;
    memset(chat,0,sizeof(chat));
    chat[HEAD].front=HEAD; chat[HEAD].back=TAIL;
    chat[TAIL].front=HEAD; chat[TAIL].back=TAIL;
    chat[HEAD].pro=-INF-1; chat[TAIL].pro=-INF-1;
}

void Add(int u)
{
    if(pc.count(u))
    {
        puts("same priority.");
        return ;
    }
    pc.insert(u);
    chat[id].w=0; chat[id].pro=u;
    chat[id].front=chat[TAIL].front;
    chat[id].back=TAIL;
    chat[chat[TAIL].front].back=id;
    chat[TAIL].front=id;
    id++;
    puts("success.");
}

void Close(int u)
{
    if(pc.count(u)==0)
    {
        puts("invalid priority.");
        return ;
    }
    pc.erase(u);
    if(alwayson==u) alwayson=-1;
    int pos=HEAD;
    for(pos=HEAD;pos!=TAIL;pos=chat[pos].back)
    {
        if(chat[pos].pro==u) break;
    }
    int bc=chat[pos].back;
    int ft=chat[pos].front;
    chat[bc].front=ft;
    chat[ft].back=bc;
    printf("close %d with %I64d.\n",chat[pos].pro,chat[pos].w);
}

void Chat(int w)
{
    if(chat[HEAD].back==TAIL)
    {
        puts("empty.");
        return ;
    }
    puts("success.");
    int u=-1;
    if(alwayson!=-1) u=alwayson;
    else u=chat[chat[HEAD].back].pro;
    int pos=HEAD;
    for(pos=HEAD;pos!=TAIL;pos=chat[pos].back)
    {
        if(chat[pos].pro==u) break;
    }
    chat[pos].w+=w;
}

void Rotate(int x)
{
    if(x<1||x>pc.size())
    {
        puts("out of range.");
        return ;
    }
    puts("success.");
    int pos=HEAD,i=0;
    for(pos=HEAD;ichat[mxp].pro)
        {
            mxp=pos;
        }
    }
    pos=mxp;
    ///split
    int bc=chat[pos].back;
    int ft=chat[pos].front;
    chat[bc].front=ft;
    chat[ft].back=bc;
    ///merge
    chat[pos].front=HEAD;
    chat[pos].back=chat[HEAD].back;
    chat[chat[HEAD].back].front=pos;
    chat[HEAD].back=pos;
}

void Choose(int u)
{
    if(pc.count(u)==0)
    {
        puts("invalid priority.");
        return ;
    }
    puts("success.");
    int pos=HEAD;
    for(pos=HEAD;pos!=TAIL;pos=chat[pos].back)
    {
        if(chat[pos].pro==u) break;
    }
    ///split
    int bc=chat[pos].back;
    int ft=chat[pos].front;
    chat[bc].front=ft;
    chat[ft].back=bc;
    ///merge
    chat[pos].front=HEAD;
    chat[pos].back=chat[HEAD].back;
    chat[chat[HEAD].back].front=pos;
    chat[HEAD].back=pos;
}

void Top(int u)
{
    if(pc.count(u)==0)
    {
        puts("invalid priority.");
        return ;
    }
    puts("success.");
    alwayson=u;
}

void Untop()
{
    if(alwayson==-1)
    {
        puts("no such person.");
        return ;
    }
    alwayson=-1;
    puts("success.");
}

void saybyebye()
{
    if(alwayson!=-1)
    {
        int p=HEAD;
        for(p=HEAD;p!=TAIL;p=chat[p].back)
        {
            if(chat[p].pro==alwayson) break;
        }
        if(chat[p].w) printf("Bye %d: %I64d\n",chat[p].pro,chat[p].w);
    }
    int pos=HEAD;
    for(pos=chat[HEAD].back;pos!=TAIL;pos=chat[pos].back)
    {
        if(chat[pos].pro!=alwayson&&chat[pos].w)
            printf("Bye %d: %I64d\n",chat[pos].pro,chat[pos].w);
    }
}

int main()
{
    int T_T;
    scanf("%d",&T_T);
    while(T_T--)
    {
        init();
        scanf("%d",&n);
        for(int i=0;i