首页 > ACM题库 > HDU-杭电 > HDU 3645-Code Management System[解题报告]HOJ
2014
11-30

HDU 3645-Code Management System[解题报告]HOJ

Code Management System

问题描述 :

Jack’s company has a very long program to modify. Each programmer edits some lines of that program and cannot add or delete any lines. A programmer can do three kinds of operations as below:

- SYNC: At the beginning, every programmer must do this to download the whole program from the code center to their local machine. This operation only executes once for each programmer.

- MODIFY: Modify a line of the code. The modification work will be temporarily done on the local computer.

- SUBMIT: Submit one’s whole local code to the code center. The code center will handle all possible changes and then send the whole newest program back to the submitter. We assume that the time duration of handling changes and sending back can be omitted.

The code center records the time and the performer of every operation.
As you see, a programmer can get the program from the code center only when he performs a SYNC or a SUBMIT operation. We call the version in the code center “standard version.” The code center keeps only ONE standard version.

Imagining there are two programmers who download the same version of the program and they both modify the ith line. Then they both submit their programs. Now what will the ith line be in the standard version? Jack figures out a rule. He gives each programmer a unique priority. When a programmer (Let’s name him Tom) modifies the ith line and then submit his program, the code center will handle the content of the ith line following the rules below:

1. If there was no accepted modification on the ith line before, Tom’s modification will be accepted. That means, the ith line in the standard version becomes the same as the ith line in the program submitted by Tom, and so Tom becomes the author of this line.
2. Otherwise, if the time of the last accepted modification on the ith line, is earlier than the time when Tom got the program from code center last time (Tom can get the program by SYNC or SUBMIT operation), Tom’s modification will be accepted. This situation means that there was no newly accepted modification on the ith line during the time from the ith line’s last accepted modification to Tom’s submission.
3. Otherwise, if Tom’s priority is higher than the priority of the last author of the ith line, Tom’s modification will be accepted.
4. In other cases, Tom’s modification on the ith line this time will be ignored and never be processed again.
5. If Tom’s modification was accepted, the code center would record the modification time of the ith line as the time when Tom’s SUBMIT operation happened.

Please note that a programmer can modify multiple lines before he submits, and his modification on some lines may be accepted, but on the other lines may be ignored.

For example, Alice and Bob are two programmers. Alice’s priority is 1 and Bob’s is 2(2 is higher than 1). In following case A and B, Bob’s modification on the first line will be accepted. However, Alice’s modification will be ignored in Case C but will be accepted in Case D.

Case A
[2010/07/18 12:00:00] Alice SYNC
[2010/07/18 12:00:01] Bob SYNC
Alice and Bob are editing the first line.
[2010/07/18 12:05:00] Alice SUBMIT
[2010/07/18 12:06:00] Bob SUBMIT

Case B
[2010/07/18 12:00:00] Alice SYNC
Alice is editing the first line.
[2010/07/18 12:05:00] Alice SUBMIT
[2010/07/18 12:05:01] Bob SYNC
Bob is editing the first line
[2010/07/18 12:06:00] Bob SUBMIT

Case C
[2010/07/18 12:00:00] Alice SYNC
[2010/07/18 12:00:02]Bob SYNC
Alice and Bob are editing the first line.
[2010/07/18 12:05:00]Bob SUBMIT
[2010/07/1812:06:00]Alice SUBMIT

Case D
[2010/07/18 12:00:00] Bob SYNC
Bob is editing the first line.
[2010/07/18 12:05:00]Bob SUBMIT
[2010/07/18 12:05:01]Alice SYNC
Alice is editing the first line
[2010/07/18 12:06:00]Alice SUBMIT

You need to help Jack to figure out who is the last author of every code line in the final standard version of the program.

输入:

The input contains several test cases.
For each test case, the first line contains an integer n (0<n<=10000), representing the number of programmers. The following lines contain their working details.

For each programmer, the first line contains a string and two integers pi and qi. The string represents his/her name, which only contains letters. The length of each name is less than 30. pi is his/her priority number and qi is the number of operations his/her has done. Each of the following qi lines contains a single operation. The format is as following:

“[yyyy/mm/dd hh:mm:ss] OPERATION”

There is a blank between day(dd) and hour(hh), as well as the right square bracket and OPERATION. The OPERATION has three formats: “SYNC”, “MODIFY line_id” and “SUBMIT”. The line_id was an integer representing the certain line number on which this modification happens. There is a blank between MODIFY and line_id. There is no extra blank.

The line numbers and priority numbers are integers from 0 to 231-1. The sum of all the qi is less than or equal to 50000. You can assume that all operations happen in different time.

The input file ends by a single 0 in a line.

输出:

The input contains several test cases.
For each test case, the first line contains an integer n (0<n<=10000), representing the number of programmers. The following lines contain their working details.

For each programmer, the first line contains a string and two integers pi and qi. The string represents his/her name, which only contains letters. The length of each name is less than 30. pi is his/her priority number and qi is the number of operations his/her has done. Each of the following qi lines contains a single operation. The format is as following:

“[yyyy/mm/dd hh:mm:ss] OPERATION”

There is a blank between day(dd) and hour(hh), as well as the right square bracket and OPERATION. The OPERATION has three formats: “SYNC”, “MODIFY line_id” and “SUBMIT”. The line_id was an integer representing the certain line number on which this modification happens. There is a blank between MODIFY and line_id. There is no extra blank.

The line numbers and priority numbers are integers from 0 to 231-1. The sum of all the qi is less than or equal to 50000. You can assume that all operations happen in different time.

The input file ends by a single 0 in a line.

样例输入:

2
Alice 1 3
[2010/07/18 12:00:00] SYNC
[2010/07/18 12:01:00] MODIFY 1
[2010/07/18 12:05:00] SUBMIT
Bob 2 3
[2010/07/18 12:00:01] SYNC
[2010/07/18 12:01:30] MODIFY 1
[2010/07/18 12:06:00] SUBMIT
2
Alice 1 3
[2010/07/18 12:05:01] SYNC
[2010/07/18 12:05:30] MODIFY 1
[2010/07/18 12:06:00] SUBMIT
Bob 2 3
[2010/07/18 12:00:01] SYNC
[2010/07/18 12:01:30] MODIFY 1
[2010/07/18 12:05:00] SUBMIT
0

样例输出:

1 [2010/07/18 12:06:00] BY Bob
END
1 [2010/07/18 12:06:00] BY Alice
END

Hint
The sample cases correspond to pervious Case A and Case D.

#include <cstdio>
#include <cstring>
#include <map>
#include <vector>
#include <algorithm>

using namespace std;

#define MAXN 10010
#define MAXM 50010

struct ti //ʱ��
{
 int y,m,d,h,f,s;
};

struct eugin //Ԥ����op
{
 ti mytime;
 int ren,op;//op: -1==SYNC��-2==SUBMIT
};

struct job //��¼ÿ���˵IJ���
{
 map <int,int> h;
 vector <int> line;
 ti last;
 int sum;
};

struct cyr
{
 ti mytime;
 int ren,hang;
};

struct person
{
 char name[36];
 int p;//���ȼ�
};

map <int,int> hash; //�����Ӧ��int
person per[MAXN];
int up;//����hash���ֵ
int m,n;
cyr ans[MAXM];
eugin c[MAXM];
job dps[MAXN];

bool operator < (ti q,ti w)
{
 if (q.y<w.y) return true;
 if (q.y>w.y) return false;
 if (q.m<w.m) return true;
 if (q.m>w.m) return false;
 if (q.d<w.d) return true;
 if (q.d>w.d) return false;
 if (q.h<w.h) return true;
 if (q.h>w.h) return false;
 if (q.f<w.f) return true;
 if (q.f>w.f) return false;
 if (q.s<w.s) return true;
 if (q.s>w.s) return false;
 return false;
}

bool operator < (eugin q,eugin w)
{
 if (q.mytime<w.mytime) return true;
 return false;
}

bool operator < (cyr q,cyr w)
{
 if (q.hang<w.hang) return true;
 return false;
}

inline void work()
{
 int i,x,j,l;
 for (i=1;i<=m;i++) ans[i].ren=-1;
 for (i=1;i<=m;i++)
 {
 x=c[i].ren;
 if (c[i].op==-1)
 {
 dps[x].h.clear();
 dps[x].line.clear();
 dps[x].sum=0;
 dps[x].last=c[i].mytime;
 }
 else if (c[i].op==-2)
 {
 for (j=0;j<dps[x].line.size();j++)
 {
	l=dps[x].line[j];
	if (ans[l].ren==-1)
	{
	 ans[l].ren=x;
	 ans[l].mytime=c[i].mytime;
	}
	else if (per[ans[l].ren].p<per[x].p)
	{
	 ans[l].ren=x;
	 ans[l].mytime=c[i].mytime;
	}
	else if (ans[l].mytime<dps[x].last)
	{
	 ans[l].ren=x;
	 ans[l].mytime=c[i].mytime;
	}
 }
 dps[x].h.clear();
 dps[x].line.clear();
 dps[x].sum=0;
 dps[x].last=c[i].mytime;
 }
 else
 {
 int temp;
 if (dps[x].h[c[i].op]==0)
 {
	dps[x].sum++;
	dps[x].h[c[i].op]=dps[x].sum;
 dps[x].line.push_back(c[i].op);
 }
 else
 {
	temp=dps[x].h[c[i].op]-1;
	dps[x].line[temp]=c[i].op;
 }
 }
 }
}

inline void output()
{
 int i;
 ti t;
 sort(ans+1,ans+1+up);
 for (i=1;i<=up;i++)
 {
 if (ans[i].ren==-1) continue;
 if (ans[i].hang==-1) printf("0 ");
 else printf("%d ",ans[i].hang);
 t=ans[i].mytime;
 printf("[%d/%02d/%02d %02d:%02d:%02d] BY ",t.y,t.m,t.d,t.h,t.f,t.s);
 printf("%s\n",per[ans[i].ren].name);
 }
 puts("END");
}

int main()
{
 // freopen("a.txt","r",stdin);
 int i,x,j,temp;
 char e[10];
 ti t;
 scanf("%d",&n);
 while (n)
 {
 hash.clear();
 up=0;
 j=0;
 for (i=1;i<=n;i++)
 {
 scanf("%s %d %d",per[i].name,&per[i].p,&x);
 getchar();
 while (x--)
 {
	j++;
	scanf("[%d/%d/%d %d:%d:%d] %s",&t.y,&t.m,&t.d,&t.h,&t.f,&t.s,e);
	c[j].mytime=t;
	c[j].ren=i;
	if (e[1]=='Y')
	 c[j].op=-1;
	else if (e[1]=='U')
	 c[j].op=-2;
	else 
	{
	 scanf("%d",&c[j].op);
	 temp=c[j].op;
	 if (hash[temp]==0)
	 {
	 up++;
	 hash[temp]=up;
	 ans[up].hang=temp;
	 c[j].op=up;
	 }
	 else c[j].op=hash[temp];
	}
	getchar();
 }
 }
 sort(c+1,c+1+j);
 m=j;
 work();
 output();
 //-----
 scanf("%d",&n);
 }
 return 0;
}

  1. 有一点问题。。后面动态规划的程序中
    int dp[n+1][W+1];
    会报错 提示表达式必须含有常量值。该怎么修改呢。。

  2. I go through some of your put up and I uncovered a good deal of expertise from it. Many thanks for posting this sort of exciting posts

  3. Gucci New Fall Arrivals

    This is really nice to know. I hope it will be successful in the future. Good job on this and keep up the good work.

  4. 第二块代码if(it != mp.end())应改为if(it != mp.end() && (i+1)!=(it->second +1));因为第二种解法如果数组有重复元素 就不正确