QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #348625 | #8230. Submissions | Freeuni1# | WA | 165ms | 13092kb | C++14 | 6.1kb | 2024-03-09 20:04:40 | 2024-03-09 20:04:40 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct cont {
string name;
int num;
int pen;
int maxPen;
int minPen;
int dePen;
int adPen;
int canMinus;
int canPlus;
cont(){
name = "#";
}
cont(string name) {
num = 0;
minPen = 1000000000000000000ll;
dePen = 1000000000000000000ll;
adPen = 0;
pen = 0;
canPlus = 0;
canMinus = 0;
maxPen = 0;
this->name = name;
}
bool operator<(cont &b) {
return num == b.num ? pen < b.pen : num > b.num;
}
bool operator==(cont &b) {
return num == b.num && pen == b.pen;
}
};
map<pair<string, string>, int> q, prePen, lmao, mp;
map<pair<string, string>, int> acc;
int tim[100005];
string qu[100005][3];
map<string, cont> w;
set<string> scr;
void getW(cont &wGold, cont a) {
if (a.canMinus) {
a.num --;
a.pen -= a.dePen;
} else {
a.pen += a.maxPen;
}
if (wGold.name == "#" || a < wGold) {
wGold = a;
}
}
main() {
ios::sync_with_stdio(0);
int t;
cin >> t;
while (t --) {
q.clear();
w.clear();
prePen.clear();
lmao.clear();
mp.clear();
acc.clear();
scr.clear();
int n;
cin >> n;
int sc = 0, maxBad = 0;
for (int i = 0; i < n; i ++) {
string name, task, stat;
int tm;
cin >> name >> task >> tm >> stat;
tim[i] = tm;
qu[i][0] = name;
qu[i][1] = task;
qu[i][2] = stat;
if (stat[0] == 'a') {
acc[{name, task}] ++;
scr.insert(name);
}
}
for (int i = 0; i < n; i ++) {
string name = qu[i][0],
task = qu[i][1],
stat = qu[i][2];
//cout << name << "!!";
int tm = tim[i];
if (q[{name, task}] == 0) {
if (!w.count(name)) {
w[name] = cont(name);
}
}
if (stat[0] == 'r') {
if (scr.find(name) == scr.end()) {
maxBad = max(maxBad, tm - 20 * q[{name, task}]);
}
if (acc.find({name, task}) == acc.end()) {
w[name].minPen = min(w[name].minPen, tm);
w[name].canPlus ++;
}
if (q[{name, task}] == 0) {
mp[{name, task}] = tm;
}
if (q[{name, task}] <= 0) {
q[{name, task}] --;
} else {
q[{name, task}] ++;
}
//cout <<"---> REJ "<< name << " " << task << " " << q[{name, task}] << endl;
} else {//cout <<"---> ACC "<< name << " " << task << endl;
if (q[{name, task}] <= 0) {
if (w[name].num == 0)sc ++;
w[name].canMinus ++;
w[name].num ++;
int pen = tm - (q[{name, task}] * 20);
if (acc[{name, task}] == 1) {
w[name].dePen = min(w[name].dePen, pen);
}
if (q[{name, task}] < 0) {
w[name].adPen = max(w[name].adPen, pen - mp[{name, task}]);
}
w[name].pen += pen;
prePen[{name, task}] = pen;
q[{name, task}] *= -1;
q[{name, task}] ++;//cout << name << " " << q[{name, task}]<< endl;
}
else {
if (!lmao[{name, task}]) {
w[name].canMinus --;
lmao[{name, task}] = 1;
w[name].maxPen = max(w[name].maxPen, tm + (q[{name, task}] * 20) - prePen[{name, task}]);
}
}
}
}
vector<cont> res;
for (auto it : w) {
res.push_back(it.second);
}
sort(res.begin(), res.end());
vector<string> pas;
int lastPlace = 0;
cont lastCont = cont(), wGold = cont(), lp1 = cont();
int gold = min(36ll, (sc + 9) / 10);
for (int i = 0; i < res.size(); i ++) {
//cout <<">>"<< res[i].name << " " << res[i].num << " " << res[i].pen << endl;
int place = i + 1;
if (gold == 0) {
pas.push_back(res[i].name);
continue;
}
if (lastPlace && res[i] == res[i-1]) {
place = lastPlace;
}
if (place == gold + 1) lp1 = res[i];
if (place <= gold) {
pas.push_back(res[i].name);
getW(wGold, res[i]);
//cout << "!!" << gold << " " << sc << endl;
lastCont = res[i];
lp1 = res[i];
}
//cout << place << " " << endl;
if (place == gold + 1 && ((res[i] < wGold || res[i] == wGold) && (wGold.num > 0 || min(35ll, (sc + 8) / 10) == gold))) {
pas.push_back(res[i].name);
//cout << "!!!"<<min(35ll, (sc + 8) / 10) << " "<<gold << " " << (res[i] < wGold || res[i] == wGold) << endl;
} else if (place == gold + 1 && sc != res.size() && min(35ll, (sc + 10) / 10) > gold) {
if (res[i].num > 1 || res[i].pen <= maxBad)pas.push_back(res[i].name);
//cout << "!!";
}
else if (place > gold) {
int pl = 0;
if (res[i].canPlus) {
res[i].num ++;
res[i].pen += res[i].minPen;
if (res[i].num == 1 && min(35ll, (sc + 10) / 10) > gold) pl = 1;
} else {
res[i].pen -= res[i].adPen;
}
//cout << "??" << res[i].name << res[i].num <<" " << lastCont.num << " " << gold<< endl;
if ((pl == 1 && (res[i] < lp1 || res[i] == lp1)) || (res[i] < lastCont || res[i] == lastCont)) {
//cout <<"??";
pas.push_back(res[i].name);
}
}
lastPlace = place;
}
cout << pas.size() << endl;
for (auto name : pas) {
cout << name << " ";
}
cout << endl;
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 12996kb
input:
2 5 TSxingxing10 G 0 rejected TSxingxing10 B 83 accepted aoliaoligeiliao J 98 accepted TS1 J 118 accepted TS1 B 263 accepted 12 AllWayTheNorth A 0 rejected YaoYaoLingXian Y 10 accepted XuejunXinyoudui1 X 200 rejected XuejunXinyoudui1 X 200 accepted LetItRot L 215 accepted AllWayTheNorth W 250 accept...
output:
2 TS1 TSxingxing10 4 AllWayTheNorth ImYourFan LetItRot XuejunXinyoudui1
result:
ok 2 test cases ok. (2 test cases)
Test #2:
score: 0
Accepted
time: 5ms
memory: 12936kb
input:
2 2 jiangly_fan A 1 accepted jiangly B 23 accepted 3 conqueror_of_tourist A 1 accepted conqueror_of_tourist A 2 accepted tourist B 23 accepted
output:
2 jiangly_fan jiangly 1 conqueror_of_tourist
result:
ok 2 test cases ok. (2 test cases)
Test #3:
score: 0
Accepted
time: 5ms
memory: 12992kb
input:
2 13 A A 1 accepted A X 1 accepted K K 1 rejected B B 2 accepted C C 2 accepted D D 2 accepted E E 2 accepted F F 2 accepted G G 2 accepted H H 2 accepted I I 2 accepted J J 2 accepted K K 2 rejected 12 A A 1 accepted A X 1 accepted B B 2 accepted C C 2 accepted D D 2 accepted E E 2 accepted F F 2 a...
output:
11 A B C D E F G H I J K 1 A
result:
ok 2 test cases ok. (2 test cases)
Test #4:
score: 0
Accepted
time: 0ms
memory: 13056kb
input:
2 11 A A 1 accepted B B 1 accepted C C 2 accepted D D 2 accepted E E 2 accepted F F 2 accepted G G 2 accepted H H 2 accepted I I 2 accepted J J 2 accepted K K 2 accepted 12 A A 1 accepted A X 1 accepted K K 1 rejected B B 2 accepted C C 2 accepted D D 2 accepted E E 2 accepted F F 2 accepted G G 2 a...
output:
2 A B 2 A K
result:
ok 2 test cases ok. (2 test cases)
Test #5:
score: 0
Accepted
time: 127ms
memory: 13092kb
input:
100000 1 M3JytWoaEXxkACy_mBAQ R 111 accepted 1 sQ O 151 accepted 1 JinbrcS58gNEE5yTSkT B 140 accepted 1 cklwBY V 243 accepted 1 v_o42YmvEKFwy Q 260 rejected 1 ftQVK8S_um22w K 265 accepted 1 _bQBeFeDpYQhvZcLf9l3 Z 147 accepted 1 KvDcEAIDN A 75 rejected 1 H3MUK6 A 101 rejected 1 gxYo_oCFn2J8aIben U 54...
output:
1 M3JytWoaEXxkACy_mBAQ 1 sQ 1 JinbrcS58gNEE5yTSkT 1 cklwBY 1 v_o42YmvEKFwy 1 ftQVK8S_um22w 1 _bQBeFeDpYQhvZcLf9l3 1 KvDcEAIDN 1 H3MUK6 1 gxYo_oCFn2J8aIben 1 _isnlUGK0ddI 1 BERcVjyCp 1 6In2do_50ylch 1 f0r3SXc6brMjT 1 7njYOapSwvogA 1 x 1 y1w3KvxylfxwprRBYw 1 aGedzS 1 iPo0GDhIF 1 4Vf...
result:
ok 100000 test cases ok. (100000 test cases)
Test #6:
score: -100
Wrong Answer
time: 165ms
memory: 13036kb
input:
10000 42 Bzs0PiQMXGZ5rRZ_2D G 2 accepted 9XtB_VIfbRRL E 11 accepted FVJL M 13 rejected a S 19 accepted tsd Z 20 rejected MyCqVEg1ONjZ U 22 accepted 6SgZMn N 51 rejected Qua1Pti3vKhyQKDUm P 54 accepted i29 M 63 accepted zPqu D 68 rejected xx2yiu6x C 71 rejected fYuK1KNkuyO5HRCq L 76 rejected tXWpYVqj...
output:
3 Qua1Pti3vKhyQKDUm fYuK1KNkuyO5HRCq tsd 2 t3 JP 2 fhYPGC8W82NwJTQL 77sgqpbTIr_Zt1 2 3BQ pVWDEz 2 buCeoOotAkV8DaFD6 tg 1 UkXQ3iaNJ 2 vwfw ALTqPt7JUSLrl 1 QTEzV6tp 3 9cy_y_RNRwex8j7224hz wJlbqIU 4e1l0pO8eFjZwkDo 2 eiuF7a_ 6mbCu5zA 1 xy6QBr8ECi 3 ldaKLZb1oS1sS PezeyUurYoz7N1iGU _Yej1PrINtyd...
result:
wrong answer the numbers are different in the case 1. (test case 1)