ACM systemLogin and star it!Submit: 283 Accepted:39Time Limit: 3000MS Memory Limit: 65535KDescription
912实验室最近设计了一种能够自动控制进程调度的系统，英文名是Automatic Control Machinery，简称ACM。该系统具有很多优秀的功能，为了方便大家的理解，这里先介绍一下关于进程、进程调度的常识。
1、 每个进程需要占用1个或多个单位内存空间，然而令人惊叹的是，在912实验室开发的平台上，一个进程只需要占用1个单位内存！
2、 每个进程用三个参量来表示，编号、权值、内存地址(0x00000000~0xFFFFFFFF)。
3、 所有的进程都被集中到一个名为“进程池”的地方，ACM系统可以实时的从进程池中选取最高优先级的进程。
4、 我们定义进程之间的优先级如下，如果两个进程的权值不同，权值大的优先级高；如果权值相同，编号小的进程优先级高。
现在就要介绍下ACM系统的详细功能了，它总共有4种操作：
1、 Get，返回当前最高优先级的进程信息(编号、权值、内存地址)
2、 Creat ID W ADDRESS，在进程池中创建一个编号为ID，权值为W，地址为ADDRESS的进程
3、 Kill ID，无条件的中止编号为ID的进程
4、 Change ID W，改变编号为ID的进程的权值
由于ACM系统尚在理论研究阶段，所以我们希望热心的你帮忙实现该系统，以具备上述所说的功能。当然，你的系统应该有一定的健壮性，至少能够对错误的操作给出异常提示。
Input
输入包含多组测试数据。
首先第一行输入一个数T(T<=10)，表示总共有T组测试数据。
接下来是每组测试数据，第一行是一个数N(N<=100000)，表示总共有N个不同编号(编号从0到N-1)的进程。然后是一个数n(n& lt;=100)，表示ACM系统启动的时候，需要初始化的n个进程。接着n行，都是id、w、address这样的形式出现，表示这n个进程的详细信 息。
紧接着是一个数M(M<=200000)，表示总共有M个操作。接着M行，描述的是下面四种中的某一种操作：
1、 Get
2、 Creat ID W ADDRESS
3、 Kill ID
4、 Change ID W
Output
首先，输出Case X：其中X代表是第X组数据(具体格式参照样例)。
对于Get操作，你需要返回最高优先级进程的信息 或 异常提示(进程池中无进程)。
对于Creat、Kill、Change操作，如果出现了错误操作(新添加进程的编号已经存在了、新添加进程的地址已经被使用了、中止根本不存在的进程、改变不存在进程的权值)，给出异常提示，并忽略该操作；如果上述三种操作都正确，不需要输出任何东西。
对于所有的异常，只需输出“ERROR！”即可。
Sample Input
2
1
1
0 3 0xAAAAAAAA
3
Creat 0 2 0xFFFFFFFF
Kill 0
Get
3
2
0 1 0x11112222
1 2 0x22221111
5
Get
Change 2 2
Kill 1
Get
Kill 1
Sample Output
Case 1:
ERROR!
ERROR!
Case 2:
1 2 0x22221111
ERROR!
0 1 0x11112222
ERROR!
Hint
巨大的输入输出，推荐scanf和printf
Source
humanjustic
题目链接：
http://boj.me/onlinejudge/showproblem.php?problem_id=1295题目要求：
实现某种数据结构，性质如下。
可用于存储元素，元素有三个属性，编号（整数），权值（整数），地址（十六进制表示的整数）。
元素有偏序关系，权值大者优先，编号小者优先（二级比较）。
能够实现如下功能。
1初始化，可以初始化结构中N个元素（利用三个数值）。
2插入新元素，可返回错误信息。（编号重复的报错，地址重复的报错）
3删除已有元素，可返回错误信息。（编号不存在的报错）
4返回最高优先级元素，可返回错误信息。（结构中为空，即无元素报错）
5改变元素的权值，可返回错误信息。（对应编号不存在的报错）
先说感想：
数据结构神马的，要有想象力，但是又不像贪心题和DP题那样需要YY能力。只要YY出能够优化复杂度的结构来即可。（前提是足够的数据结构知识储备和强大的代码能力）
话说这道题的那个神奇的内存地质。。。十六进制数，让我好好学习了一下scanf、printf读入输出指定格式十六进制数，以及cout的格式输出。编程语言的开创者们真是给想好了各种内部优化，不用小菜我再去纠结格式输出的问题。（不然用字符串存地址，铁定超时啊）
Solution：
直观解，该数据结构为堆。根据CLRS，可实现其build、heapify、increase、maximum、insert、delete等全部操作，这些操作的复杂度均为O(logN)（build除外，O(N * LogN)。
但问题在于，传统heap无法实现对于特定编号元素的O(LogN)的查找。
所以配合HASH（两种偷懒的HASH方式，一为int标记数组，二为map映射，分别为O(1)（标记）,O(LogN)（红黑树））。
具体实现：
int to[]，用标记数组记录对应编号元素（数组下标）在堆中的位置（还是数组下标，不过是堆的）
map<unsigned long,int> add，用map将地址映射，用于记录指定地址的存在性
struct node（为了元素的偏序关系才要这个）
（以下每个函数在操作的同时，要维护to数组和add的HASH）
inc函数，对于堆中特定位置的元素，增加其权值到指定值，再逆向维护堆的性质
insert函数，将新加入的元素插在堆尾，再用inc函数增加权值并维护堆性质
heapify函数，从特定位置起，向下正向维护堆性质
del函数，交换堆尾元素与被删元素，再用heapify维护
change函数，如果是权值增加操作则逆向维护堆，反之则正向维护堆
所有函数实现的过程中通过对to数组和add哈希的查找来判断报错与否
#include <iostream>
#include <cstdio>
#include <map>
#include <cstring>
#include <iomanip>
#define left(i) ((i) << 1)
#define right(i) (((i) << 1) + 1)
#define parent(i) ((i) >> 1)
#define WRONG printf("ERROR!\n")
using namespace std;
typedef unsigned long ul;
struct node
{
int num,value;
long long addr;
node(){}
node(int _num,int _value,ul _addr)
{
num = _num;
value = _value;
addr = _addr;
}
bool friend operator < (const node &a,const node &b)
{
return (a.value < b.value) || (a.value == b.value && a.num > b.num );
}
void print()
{
printf("%d %d 0x%08X\n",num,value,addr);
//cout.fill('0');
//cout << setw(8) << HEX << addr << '\n';
/*for(int i = 31;i >= 0;i -= 4)
{
int temp = 0;
for(int j = 0;j < 4;j++)
temp += (((value >> (i - j)) & 1) * (1 << (4 - j)));
printf("%c",(temp > 9) ? (temp - 10 + 'A') : (temp + '0'));
}
printf("\n");*/
}
};
struct heap
{
map <ul,int> add;
int to[100005];
//map <int , int> to;//id to index
node * ele[100005];
int size;
heap(int N){size = 0;for(int i = 0;i <= N;i++)to[i] = 0;}
bool insert(int num,int value,ul addr)
{
if(to[num] != 0 || add[addr] != 0)//id existed || addr existed
.
return false;//judge
ele[++ size] = new node;
inc(size,num,value,addr);
return true;
}
bool del(int id)
{
int pos;
//cout << "\t\t\tid : " << to[id] << endl;
if(to[id] == 0)//delete doesn't exist
return false;
//cout << "\t\t\tpos : " << to[id] << " id : " << id << endl;
pos = to[id];
to[ele[size] -> num] = pos;
to[id] = 0;
//cout << "\t\t\tpos : " << to[id] << " id : " << id << endl;
add[ele[pos] -> addr] = 0;
swap(ele[pos],ele[size]);
delete ele[size];
ele[size] = NULL;
size--;
heapify(pos);
return true;
}
bool top()//empty
{
if(size < 1)
return false;
else
{
ele[1] -> print();
return true;
}
}
void heapify(int pos)
{
int l = left(pos),r = right(pos),big;
if(l <= size && *ele[pos] < *ele[l])
big = l;
else
big = pos;
if(r <= size && *ele[big] < *ele[r])
big = r;
if(big != pos)
{
swap(ele[big],ele[pos]);
swap(to[ele[big] -> num],to[ele[pos] -> num]);
/*cout << " ---------------------------" << endl;
cout << ele[big] -> num << " id " << ele[pos] -> num << endl;
cout << " ---------------------------" << endl;*/
heapify(big);
}
}
void inc(int pos,int id,int value,ul ad)
{
ele[pos] -> num = id;
ele[pos] -> value = value;
ele[pos] -> addr = ad;
to[id] = pos;
add[ad] ++;
int t = pos,pt = parent(pos);
while(pt >= 1 && !(*ele[t] < *ele[pt]))
{
swap(ele[t],ele[pt]);
swap(to[ele[t] -> num],to[ele[pt] -> num]);
t = pt;
pt = parent(t);
}
}
bool change(int num,int value)
{
if(to[num] == 0)
return false;
int pos = to[num];
if(ele[pos] -> value > value)
{
ele[pos] -> value = value;
heapify(pos);
}
else if(ele[pos] -> value == value)
;
else
{
ele[pos] -> value = value;
int t = pos,pt = parent(pos);
while(pt >= 1 && !(*ele[t] < *ele[pt]))
{
swap(ele[t],ele[pt]);
swap(to[ele[t] -> num],to[ele[pt] -> num]);
t = pt;
pt = parent(t);
}
}
return true;
}
};
void solve()
{
int N,n,m;
scanf("%d",&N);
scanf("%d",&n);
heap s(N);
for(int i = 0;i < n;i++)
{
int a,b;
ul c;
scanf("%d %d %X",&a,&b,&c);
s.insert(a,b,c);
/*cout << endl <<"--------------------AA" << " size : " << s.size << endl;
for(int j = 1;j <= s.size;j++)
s.ele[j] -> print();
cout <<"--------------------AA" << endl << endl;*/
}
scanf("%d",&m);
for(int i = 0;i < m;i++)
{
//cout << "option : " << i + 1 << endl;
char opt[10];
scanf("%s",opt);
//cout << opt << " ";
if(!strcmp(opt,"Get"))
{
if(!s.top())
WRONG;
}
else if(!strcmp(opt,"Creat"))
{
int a,b;
ul c;
scanf("%d %d %X",&a,&b,&c);
//printf("%d %d 0x%X\n",a,b,c);
if(!s.insert(a,b,c))
WRONG;
}
else if(!strcmp(opt,"Kill"))
{
int a;
scanf("%d",&a);
//printf("%d\n",a);
if(!s.del(a))
WRONG;
}
else if(!strcmp(opt,"Change"))
{
int a,b;
scanf("%d%d",&a,&b);
//printf("%d %d\n",a,b);
if(!s.change(a,b))
WRONG;
}
/*cout << endl <<"--------------------AA" << " size : " << s.size << endl;
for(int j = 1;j <= s.size;j++)
s.ele[j] -> print();
cout <<"--------------------AA" << endl << endl;*/
}
}
int main()
{
int t;
freopen("data.in","r",stdin);
freopen("data3.out","w",stdout);
// while(scanf("%d",&t) == 1)
scanf("%d",&t);
{
for(int i = 0;i < t;i++)
{
printf("Case %d:\n",i + 1);
solve();
}
}
}