Kattis-Administrative Difficulties

Administrative Difficulties

题面

It is difficult for a spy to do his job without a decent car. The Bureau of Administrative Personnel for Cars (BAPC) spy-car rental company has a large collection of cars that spies can use and handles the resulting administration. Using cars obviously costs money: they require gasoline to operate and repairs are needed quite often, because spies tend to cause accidents a little more often than other drivers.

At the end of the year, all spies need to be billed for the usage of cars in the past year. Last week, there was a major crash in the billing system, rendering it unusable. All that could be recovered was a list of all available types of cars and a log of events for the past year. Using this information, the spy-car rental company wants to obtain a list of the costs for car usage for every spy on record. This list can then be used to send out the bills manually.

Every type of car is registered with a catalog price, the cost to pick up the car and the cost of driving that car per kilometer. The event list contains three types of events: pick-ups, returns and accidents. When a spy picks up a car, he or she must pay the pick-up cost for that car. Once the car is returned, the number of kilometers driven in the car is recorded and the spy must pay for these kilometers. If an accident occurred when the spy was using the car, repairs need to be paid for. Every accident is rated with a severity as a percentage. To repair the car, this percentage of the catalog price is billed to the spy who caused the accident. If any billed cost is fractional, it is rounded up to the next integer before being added to the bill.

The list of all available types of cars is complete. However, because of the crash, some events in the recovered event log might be missing. The spy-car rental company does not want to present spies with an inconsistent bill, so you should detect inconsistencies in the log entries for each spy. The following conditions hold for a consistent event log:

A spy will pick up a car before returning it.

A spy will always return a car they picked up.

A spy can use at most one car at a time.

Accidents can only happen when a spy is using a car.

Input

On the first line one positive number: the number of test cases, at most 100. After that per test case:

  • one line with two space-separated integers n and m (0≤n≤5000≤n≤500 and 0≤m≤100000≤m≤10000): the number of types of cars, and the number of events, respectively.
  • n lines with a string N and three integers p, q and k (1≤p≤100000,1≤q≤1000,1≤k≤1001≤p≤100000,1≤q≤1000,1≤k≤100), all separated by a space: for each type of car, its unique name, its catalog price, its pick-up cost, and its cost per kilometer driven, respectively.
  • m lines starting with one integer t (0≤t≤1000000≤t≤100000), a string S and one character e, all separated by a space: the time of the event, the name of the involved spy, and the type of event, followed by:
    • if e = ‘p’ (pick-up): a string C: the name of the type of car picked up.
    • if e = ‘r’ (return): an integer d (0≤d≤10000≤d≤1000): the distance covered in the car last picked up by spy S, in kilometers.
    • if e = ‘a’ (accident): an integer s (0≤s≤1000≤s≤100): the severity of the accident, in percents.

All names of cars and spies consist of at least 11 and at most 4040 lowercase letters. There will be at most 500 unique spy names in each test case. The events are given in chronological order.

Output

Per test case:

  • one line for every spy referenced in any of the events, containing a string and one integer, separated by a space: the name of the spy and his total car cost. If the event log for the spy is inconsistent, the total cost should be replaced by the string “INCONSISTENT”. The lines should be sorted alphabetically by the name of the spy.

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
1
2 8
bmw 5000 150 10
jaguar 7000 200 25
10 mallory p bmw
15 jb p jaguar
20 jb r 500
35 badluckbrian a 100
50 mallory a 10
55 silva p jaguar
60 mallory r 100
110 silva a 30

Sample Output

1
2
3
4
badluckbrian INCONSISTENT
jb 12700
mallory 1650
silva INCONSISTENT

思路

其实就是一个比较简单的判断加模拟。

需要注意的是同一种类的车子可以有多辆T T,一开始没注意多加了判断然后WA了。

核心是间谍,记录每个间谍现在的状态即可(incar or not)

还有一个小trick,计算车祸的赔偿的时候

​ 通过(catalog price*severity of the accident+99)/100即可算出赔偿金额

(其实最终目的只是为了纪念我竟然写了三个struct 的模拟)

代码

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <iostream>
#include <cstring>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <deque>
#include <bitset>
#include <algorithm>

using namespace std;

const double eps=1e-10;
const double pi=3.1415926535897932384626433832795;
const double eln=2.718281828459045235360287471352;

#define LL long long
#define IN freopen("in.txt", "r", stdin)
#define OUT freopen("out.txt", "w", stdout)
#define scan(x) scanf("%d", &x)
#define scan2(x, y) scanf("%d%d", &x, &y)
#define scan3(x, y, z) scanf("%d%d%d", &x, &y, &z)
#define sqr(x) (x) * (x)
#define pr(x) printf("Case %d: ",x)
#define prn(x) printf("Case %d:\n",x)
#define prr(x) printf("Case #%d: ",x)
#define prrn(x) printf("Case #%d:\n",x)
#define lowbit(x) (x&(-x))

const int maxn=10005;

struct _spy
{
string name;
bool inc;
int now;
LL cost;
_spy(string name="",bool inc=false,int now=0,LL cost=0):name(name),inc(inc),now(now),cost(cost){}
bool operator < (struct _spy p)const{return name<p.name;}
}spy[505];

struct _event
{
int time;
string name;
char flag;
LL num;
_event(int time=0,string name="",char flag=' ',LL num=0):time(time),name(name),flag(flag),num(num){}
bool operator < (struct _event p)const{return time<p.time;}
}event[maxn];

struct _car
{
string name;
LL cp,pp,kp;
_car(string name="",LL cp=0,LL pp=0,LL kp=0):name(name),cp(cp),pp(pp),kp(kp){}
}car[505];

map<string,int> sspy,ccar;
int spyy,carr;
int n,m,T,i,j,k;
string s;

int main()
{
IN;OUT;
scanf("%d",&T);
while(T--)
{
sspy.clear();ccar.clear();
scanf("%d %d\n",&n,&m);
for(i=0;i<=n;i++)car[i]=_car("",0,0,0);
spyy=carr=0;
for(i=1;i<=n;i++)
{
cin>>car[i].name;
cin>>car[i].cp>>car[i].pp>>car[i].kp;
ccar[car[i].name]=i;
}
carr=n;k=0;
for(i=1;i<=m;i++)
{
//读入部分
cin>>event[i].time>>event[i].name>>event[i].flag;
if(sspy.count(event[i].name)<=0)
{
k++;
sspy[event[i].name]=k;
spy[k]=_spy(event[i].name,false,0,0);
}
if(event[i].flag=='p')
{
cin>>s;
event[i].num=ccar[s];
}else cin>>event[i].num;
//处理部分
int sp=sspy[event[i].name];
if(spy[sp].cost<0)continue;
if(event[i].flag=='p')
{
int ca=event[i].num;
if(spy[sp].inc){spy[sp].cost=-1;continue;}
spy[sp].inc=true;
spy[sp].now=ca;
spy[sp].cost+=car[ca].pp;
continue;
}
if(event[i].flag=='r')
{
if(!spy[sp].inc){spy[sp].cost=-1;continue;}
int ca=spy[sp].now;
spy[sp].inc=false;
spy[sp].cost+=event[i].num*car[ca].kp;
continue;
}
if(event[i].flag=='a')
{
if(!spy[sp].inc){spy[sp].cost=-1;continue;}
int ca=spy[sp].now;
spy[sp].cost+=(event[i].num*car[ca].cp+99)/100;
continue;
}
}
spyy=k;
sort(spy+1,spy+spyy+1);
for(i=1;i<=spyy;i++)
{
cout<<spy[i].name;
if(spy[i].cost<0 || spy[i].inc)printf(" INCONSISTENT\n");
else printf(" %lld\n",spy[i].cost);
}
}
return 0;
}