QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#590482#8230. Submissionsucup-team3519TL 1297ms17100kbC++204.2kb2024-09-26 00:42:292024-09-26 00:42:30

Judging History

你现在查看的是最新测评结果

  • [2024-09-26 00:42:30]
  • 评测
  • 测评结果:TL
  • 用时:1297ms
  • 内存:17100kb
  • [2024-09-26 00:42:29]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define V vector
#define all0(x) (x).begin(),(x).end()
#define all1(x) (x).begin()+1,(x).end()
#define pb push_back
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define cin std::cin
#define cout std::cout
typedef long long LL;
typedef pair<int, int> pi;
typedef pair<LL, LL> pl;

//const int MN = 2e5 + 20;
const int INF = 2e9 + 1000;
const LL INFLL = 8e18 + 1000;
mt19937 mrand(chrono::steady_clock().now().time_since_epoch().count());
//模板区域~~~~~~~

//模板结束~~~~~~~

struct val {
    int num, time;
};
bool operator<(val a, val b) {
    if(a.num != b.num) return a.num > b.num;
    return a.time < b.time;
}
val operator+(val a, val b) {
    return {a.num + b.num, a.time + b.time};
}
val operator-(val a, val b) {
    return {a.num - b.num, a.time - b.time};
}


void solve() {
    int m; cin >> m;

    int tot = 0;
    map<string, int> id;
    map<int, string> str;

    set<int> ans;

    map<int, val> normal_val[26];
    map<int, int> panalty[26];
    map<int, V<val>> alt_val[26];
    map<int, val> now_val[26];
    map<int, val> sum_val; 
    map<int, int> cnt_ac[26];
    set<int> valid_team;
    V<int> teams;
    map<int, int> solved_cnt;
    map<int, int> sp;

    for(int i = 1; i <= m; i++) {
        string team; cin >> team;
        int teamid;
        if(!id.count(team)) id[team] = ++tot, str[tot] = team;
        teamid = id[team];

        teams.pb(teamid);
        char c; int time; string stname;
        cin >> c >> time >> stname;
        c -= 'A';
        int st;
        if(stname == "accepted") st = 1;
        else st = 0;

        time += panalty[c][teamid];

        if(st && cnt_ac[c][teamid] == 0) {
            valid_team.insert(teamid);
            solved_cnt[teamid]++;
            normal_val[c][teamid] = now_val[c][teamid] = {1, time};
            sum_val[teamid] = sum_val[teamid] + normal_val[c][teamid];
        }
        if(cnt_ac[c][teamid] == 0 || cnt_ac[c][teamid] == 1 && st) {
            alt_val[c][teamid].pb({1, time});
        }

        cnt_ac[c][teamid] += st;
        panalty[c][teamid] += 20;
    }

    for(int i = 0; i < 26; i++) {
        for(auto name : teams) {
            if(cnt_ac[i][name] == 1) alt_val[i][name].pb({0, 0});
        }
    }

    set<pair<val, int>> cur;
    for(auto name : teams) {
        cur.insert({sum_val[name], name}); 
    }
    int test = 0;
    auto cal_ans = [&]() -> void {
        int x = min(35, ((int)valid_team.size() + 9) / 10);
        if(x == 0) return;

        auto it = cur.begin();
        for(int i = 1; i <= x; i++) {
            ans.insert(it->se);
            it++;
        }
        if(test) {
            if(!(prev(it)->fi < sum_val[test])) {
                ans.insert(test);
            }
        }
        while(it != cur.end() && it->fi.num == prev(it)->fi.num && it->fi.time == prev(it)->fi.time) {
            ans.insert(it->se);
            sp[it->se]++;
            if(sp[it->se] >= 60) break;
            it++;
        }
    };

    cal_ans();

    auto chg = [&](int name, int c, val v) -> void {
        cur.erase({sum_val[name], name});
        val pv = now_val[c][name];
        now_val[c][name] = v;

        if(solved_cnt[name]) valid_team.erase(name);
        solved_cnt[name] -= pv.num;
        solved_cnt[name] += v.num;
        if(solved_cnt[name]) valid_team.insert(name);
        sum_val[name] = sum_val[name] - pv;
        sum_val[name] = sum_val[name] + v;

        cur.insert({sum_val[name], name});
        test = name;
    };

    for(int i = 0; i < 26; i++) {
        for(auto name : teams) {
            if(alt_val[i][name].empty()) continue;
            for(auto v : alt_val[i][name]) {
                chg(name, i, v);
                cal_ans();
            }
            chg(name, i, normal_val[i][name]);
        }
    }

    cout << ans.size() << endl;
    for(auto s : ans) cout << str[s] << " ";
    cout << endl;
}

int32_t main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) 
    solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3680kb

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
TSxingxing10 TS1 
4
AllWayTheNorth XuejunXinyoudui1 LetItRot ImYourFan 

result:

ok 2 test cases ok. (2 test cases)

Test #2:

score: 0
Accepted
time: 0ms
memory: 3828kb

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: 1ms
memory: 3700kb

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 K B C D E F G H I J 
1
A 

result:

ok 2 test cases ok. (2 test cases)

Test #4:

score: 0
Accepted
time: 1ms
memory: 3732kb

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: 287ms
memory: 3896kb

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: 0
Accepted
time: 558ms
memory: 4052kb

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:

4
tsd Qua1Pti3vKhyQKDUm fYuK1KNkuyO5HRCq xiLm0TUOF3T 
2
t3 JP 
2
fhYPGC8W82NwJTQL 77sgqpbTIr_Zt1 
2
pVWDEz 3BQ 
2
tg buCeoOotAkV8DaFD6 
1
UkXQ3iaNJ 
2
ALTqPt7JUSLrl vwfw 
1
QTEzV6tp 
3
4e1l0pO8eFjZwkDo wJlbqIU 9cy_y_RNRwex8j7224hz 
2
eiuF7a_ 6mbCu5zA 
1
xy6QBr8ECi 
3
ldaKLZb1oS1sS _Yej1PrINtydmOudwo...

result:

ok 10000 test cases ok. (10000 test cases)

Test #7:

score: 0
Accepted
time: 563ms
memory: 4008kb

input:

10000
27
bhAGFVDBjp4_Tvo U 24 accepted
bhAGFVDBjp4_Tvo O 37 rejected
bhAGFVDBjp4_Tvo D 40 accepted
bhAGFVDBjp4_Tvo H 45 accepted
bhAGFVDBjp4_Tvo B 60 rejected
bhAGFVDBjp4_Tvo J 63 accepted
bhAGFVDBjp4_Tvo M 81 rejected
bhAGFVDBjp4_Tvo M 98 rejected
bhAGFVDBjp4_Tvo D 103 rejected
bhAGFVDBjp4_Tvo Q 11...

output:

1
bhAGFVDBjp4_Tvo 
2
euenQ rl 
1
seny 
2
nLWe5xvBqfYkN 8zfFqdixKjh 
1
VDeEtfbb 
1
9PAd7wtbCZMws6u 
1
Wsfc5qold4uacAjI1y 
2
NX6GLK3Nz h68cyLwQ7drM__pSJub 
3
yOgwg U7S8zgJhR6 sdf0IGct21OeEFJ 
1
acesvM9yT 
1
2hQb 
2
3twK2MJI_ P5 
1
eGCz 
3
39GgHUPovILESCd0 tLHWIEVr5i7vlKpvlP UXRu8i 
1
20gsbZ25SsYp8 
1
...

result:

ok 10000 test cases ok. (10000 test cases)

Test #8:

score: 0
Accepted
time: 591ms
memory: 4036kb

input:

10000
2
vVflLovvnhJEO U 3 accepted
Fg P 48 rejected
12
V9UJ5hEaWiwMq3lxwKw9 P 30 accepted
CKsw M 34 rejected
dCZBzKMxgQfgBDZO R 50 rejected
A1R2kF N 54 rejected
A1R2kF X 65 accepted
HEih51ut H 68 rejected
HEih51ut J 75 rejected
l0MCFXNXlH6T2wT I 163 accepted
A1R2kF B 180 accepted
dCZBzKMxgQfgBDZO A ...

output:

1
vVflLovvnhJEO 
2
V9UJ5hEaWiwMq3lxwKw9 A1R2kF 
4
fLUS3NYE 5sFcoMh xgdxQ7t 2 
2
S25TIbMLU5FMV6ys4 2ra47EFC7LWzxTF2tSH 
2
uwm tczurXngUW 
3
gWG1aLfP1Gk DNAv Zh4tWi1QdYjTblw5 
1
qN_OnmRhGksD 
1
pAJC7fTKPJjaxPP 
2
mElj5iV4wfu Jr9Sqekor 
1
_Z13N_OO 
1
rn 
1
HhjFL6Rg 
1
2q 
5
vdFavgJoOBT4vrKWv LjvEZmSkrs...

result:

ok 10000 test cases ok. (10000 test cases)

Test #9:

score: 0
Accepted
time: 565ms
memory: 3752kb

input:

10000
4
BUqwUvN2v7co K 45 accepted
fb4ykhGx9CBzWxLcGYjf F 96 rejected
3X39YaWp0LItH14Owx R 142 rejected
7JGP4qtBonRiKpsKW U 155 rejected
3
Z0cxqdpQ69NGV5wDoht X 92 rejected
1E0aicZDqPhh E 105 accepted
a3fvTkSrKXqQipNGs4h K 261 rejected
6
LR6PY6OjDoSaZpT W 33 accepted
Et8w1E52xfM27 Q 155 accepted
LR6...

output:

1
BUqwUvN2v7co 
2
Z0cxqdpQ69NGV5wDoht 1E0aicZDqPhh 
1
LR6PY6OjDoSaZpT 
3
YX 7f b 
4
WqSH sgpEsfgf_Fd buFAkOkQ_F o7VPp 
1
coTjuCSsnonAgjYkChE 
2
clGo2Z4AMe9Qp GC0Lw1Di 
2
IrJ_n_Ym FCCHBTUTGJTbTjEb 
1
fkBpEQxhBl21ARSTVR 
1
fQzlJS9JEIS97gIIG7p4 
6
pqyDmprb2RmUBafc76eR ljfPMl71hE bLED4G7CY_M CVVvEx togG...

result:

ok 10000 test cases ok. (10000 test cases)

Test #10:

score: 0
Accepted
time: 573ms
memory: 3804kb

input:

10000
7
dBv7DiT L 42 rejected
dBv7DiT P 123 accepted
7Bj2dZF6Gy7csrXYakI T 131 rejected
9KtuO O 190 accepted
BxACEk Q 285 rejected
BxACEk Q 291 rejected
HK0pq9qsGnlkgAQT L 296 accepted
3
NQgnW3CShrFJYkKdjagN G 53 rejected
ZwZCr O 261 accepted
ZwZCr P 270 accepted
6
mbGQ7wcZYr9leKBCsFN Z 4 rejected
7...

output:

2
dBv7DiT 9KtuO 
1
ZwZCr 
2
7s1bgtS 4LUVnW93OFHOl6fJOmXK 
4
_g2LouxyEI_BXaOYQWn pz CZNz6k1QgLrHojbY upCvWQnHRgRSQQ 
3
q ungF4dKzJt290JMWNgeH t 
3
6mCVqSBpHVkrNZ SuBp7xLMGCHgk 4FjAuM44Nzaz6Tc0 
1
xXqqS7r1OU 
1
YEHiJvhHR8OmUWz 
3
m 0WZFvefoPtNo BiasA1Md2ViU 
1
MzQD 
2
MJJ4n2rC7YHRflGzEL L501za_ktc 
1
...

result:

ok 10000 test cases ok. (10000 test cases)

Test #11:

score: 0
Accepted
time: 54ms
memory: 17100kb

input:

7
110
10 A 0 accepted
0 A 100 accepted
1 A 100 accepted
2 A 100 accepted
3 A 100 accepted
4 A 100 accepted
5 A 100 accepted
6 A 100 accepted
7 A 100 accepted
8 A 100 accepted
9 A 100 accepted
0 B 100 accepted
1 B 100 accepted
2 B 100 accepted
3 B 100 accepted
4 B 100 accepted
5 B 100 accepted
6 B 10...

output:

11
10 0 1 2 3 4 5 6 7 8 9 
11
0 1 2 3 4 5 6 7 8 9 10 
11
0 1 2 3 4 5 6 7 8 9 10 
11
100 0 1 2 3 4 5 6 7 8 9 
12
100 0 1 2 3 4 5 6 7 8 9 10 
36
0 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 
35
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21...

result:

ok 7 test cases ok. (7 test cases)

Test #12:

score: 0
Accepted
time: 1297ms
memory: 4908kb

input:

1000
58
8VR4968BiWGrjt0 G 1 accepted
KfduBOJVYor3ixLgzUo Y 5 accepted
r9l9P_xyc7oagiZS0ZJ G 26 accepted
PL3OrMzXRJRVskByRHHl Y 38 accepted
7wL2M4T1PWyv9rJSdzGN N 47 rejected
Vu56KH6ZGwSm E 48 rejected
8VR4968BiWGrjt0 D 53 accepted
SI7h8yP C 57 rejected
aSVEsYSH9PJjsjSAyH N 61 accepted
D3UrdM8xI S 71...

output:

5
8VR4968BiWGrjt0 PL3OrMzXRJRVskByRHHl SI7h8yP mn0iyGyqWOakTAs1Qw umqh9D 
6
9M 6OSsIJ 3A4BJULiR9S f22a5ba_ze2qsm2_2k uxPAbOmdBcWg64Q52 EYdAeGI 
25
19Mbp qF0kRrasPk wd5q6DH XJ9p0AKseAnbt7vmR_ 9sFtbGG4oMjSgmtZh oLi8SUSfzmANlYBZxL io_4OkSzJAGEqNUfs6R Qo8l4lQKg D6SdnJFh6xFQlZehalkc lUs4Rd_AXJR2FP48 qeyR...

result:

ok 1000 test cases ok. (1000 test cases)

Test #13:

score: -100
Time Limit Exceeded

input:

100
974
qG R 0 accepted
k2K I 0 accepted
NelrCjQd_AHSw107 D 1 accepted
ybeH_JvdmCLMOGl9x K 1 accepted
h3 Q 2 accepted
9qOW O 2 accepted
v1IWHoW7Mkuce6qH Y 2 accepted
mlypVkK5Xl1KXw3o P 2 rejected
zs X 3 accepted
1Fpyq8oUYV_aNp I 3 rejected
e1bM8xUh E 3 rejected
myaSH0LCL4hD5BlAj F 4 rejected
IJETUS2...

output:

65
qG k2K NelrCjQd_AHSw107 ybeH_JvdmCLMOGl9x 9qOW mlypVkK5Xl1KXw3o e1bM8xUh IJETUS2jG jpgL7AOwwgwK4fC LhlGfI4XZ 1qXXQyXNhDyf97IT0n QW b1rD1OQRc v8ok8uFd3 Io5tMwXAJlbYL2Wikqqq 55IlpzN c tHhnCuExgbOb 2tougTgqY91VXB3 Hy551D5ZPfvBDS PlD7x1RoiUUo jjlJFal1mKsc9bV0rJ UL aOtxLwyhTOqQrGSi o_d5R9oBv QXFitGeaP...

result: