QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #712334 | #8230. Submissions | KafuuChinocpp# | WA | 197ms | 321712kb | C++14 | 6.8kb | 2024-11-05 15:21:58 | 2024-11-05 15:21:59 |
Judging History
answer
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <map>
#include <set>
#include <vector>
using namespace std;
const int max1 = 1e5;
const int inf = 0x3f3f3f3f;
int T, n, m;
string c[max1 + 5], p[max1 + 5], s[max1 + 5];
int t[max1 + 5];
map <string, int> Map_name;
string name[max1 + 5];
int cnt;
struct Node
{
int t, num;
Node () {}
Node ( int __t, int __num )
{ t = __t, num = __num; }
bool operator < ( const Node &A ) const
{
if ( t == A.t )
return num < A.num;
return t < A.t;
}
bool operator == ( const Node &A ) const
{
return t == A.t && num == A.num;
}
};
multiset <Node> tim[max1 + 5][26][2];
vector <Node> seq[max1 + 5][26];
struct Data
{
int cntpro, sumtime;
Data () {}
Data ( int __cntpro, int __sumtime )
{ cntpro = __cntpro, sumtime = __sumtime; }
bool operator < ( const Data &A ) const
{
if ( cntpro == A.cntpro )
return sumtime < A.sumtime;
return cntpro > A.cntpro;
}
bool operator == ( const Data &A ) const
{
return cntpro == A.cntpro && sumtime == A.sumtime;
}
bool operator <= ( const Data &A ) const
{
return *this < A || *this == A;
}
};
map <Data, int> bin;
Data val[max1 + 5], d[max1 + 5];
int len;
Data Calc ()
{
int lim = min((n + 9) / 10, 35);
int precnt = 0;
if ( precnt >= lim )
return Data(inf, 0);
for ( auto v : bin )
{
precnt += v.second;
if ( precnt >= lim )
return v.first;
}
return (*--bin.end()).first;
}
int sum, ans[max1 + 5];
void Work ()
{
scanf("%d", &m);
Map_name.clear(); cnt = 0;
for ( int i = 1; i <= m; i ++ )
{
cin >> c[i] >> p[i] >> t[i] >> s[i];
if ( Map_name.find(c[i]) == Map_name.end() )
{
Map_name[c[i]] = ++cnt, name[cnt] = c[i];
for ( int j = 0; j < 26; j ++ )
{
seq[cnt][j].clear();
for ( int k = 0; k < 2; k ++ )
tim[cnt][j][k].clear();
}
}
if ( s[i][0] == 'a' )
tim[Map_name[c[i]]][p[i][0] - 'A'][0].insert(Node(t[i], i));
else
tim[Map_name[c[i]]][p[i][0] - 'A'][1].insert(Node(t[i], i));
seq[Map_name[c[i]]]->push_back(Node(t[i], i));
}
n = 0; bin.clear(); len = 0;
for ( int i = 1; i <= cnt; i ++ )
{
val[i].cntpro = val[i].sumtime = ans[i] = 0;
for ( int j = 0; j < 26; j ++ )
{
if ( !tim[i][j][0].empty() )
{
++val[i].cntpro;
val[i].sumtime += (*tim[i][j][0].begin()).t;
val[i].sumtime += lower_bound(seq[i][j].begin(), seq[i][j].end(), (*tim[i][j][0].begin())) - seq[i][j].begin();
}
}
if ( val[i].cntpro )
++n;
++bin[val[i]];
// printf("i = %d val = %d %d\n", i, val[i].cntpro, val[i].sumtime);
}
d[++len] = Calc();
// printf("n = %d d : cntpro = %d sumtime = %d\n", n, d[len].cntpro, d[len].sumtime);
for ( int i = 1; i <= m; i ++ )
{
int id = Map_name[c[i]];
Data preval = val[id];
--bin[val[id]];
if ( val[id].cntpro )
--n;
if ( !tim[id][p[i][0] - 'A'][0].empty() )
{
--val[id].cntpro;
val[id].sumtime -= (*tim[id][p[i][0] - 'A'][0].begin()).t;
int rk = lower_bound(seq[id][p[i][0] - 'A'].begin(), seq[id][p[i][0] - 'A'].end(), (*tim[id][p[i][0] - 'A'][0].begin())) - seq[id][p[i][0] - 'A'].begin();
val[id].sumtime -= rk * 20;
}
if ( s[i][0] == 'a' )
{
tim[id][p[i][0] - 'A'][0].erase(tim[id][p[i][0] - 'A'][0].find(Node(t[i], i)));
tim[id][p[i][0] - 'A'][1].insert(Node(t[i], i));
}
else
{
tim[id][p[i][0] - 'A'][1].erase(tim[id][p[i][0] - 'A'][1].find(Node(t[i], i)));
tim[id][p[i][0] - 'A'][0].insert(Node(t[i], i));
}
if ( !tim[id][p[i][0] - 'A'][0].empty() )
{
++val[id].cntpro;
val[id].sumtime += (*tim[id][p[i][0] - 'A'][0].begin()).t;
int rk = lower_bound(seq[id][p[i][0] - 'A'].begin(), seq[id][p[i][0] - 'A'].end(), (*tim[id][p[i][0] - 'A'][0].begin())) - seq[id][p[i][0] - 'A'].begin();
val[id].sumtime += rk * 20;
}
if ( val[id].cntpro )
++n;
++bin[val[id]];
d[++len] = Calc();
// printf("n = %d d : cntpro = %d sumtime = %d\n", n, d[len].cntpro, d[len].sumtime);
if ( preval <= d[len] )
--ans[id];
if ( val[id] <= d[len] )
++ans[id];
// printf("id = %d ans = %d\n", id, ans[id]);
--bin[val[id]];
if ( val[id].cntpro )
--n;
if ( !tim[id][p[i][0] - 'A'][0].empty() )
{
--val[id].cntpro;
val[id].sumtime -= (*tim[id][p[i][0] - 'A'][0].begin()).t;
int rk = lower_bound(seq[id][p[i][0] - 'A'].begin(), seq[id][p[i][0] - 'A'].end(), (*tim[id][p[i][0] - 'A'][0].begin())) - seq[id][p[i][0] - 'A'].begin();
val[id].sumtime -= rk * 20;
}
if ( s[i][0] == 'a' )
{
tim[id][p[i][0] - 'A'][1].erase(tim[id][p[i][0] - 'A'][1].find(Node(t[i], i)));
tim[id][p[i][0] - 'A'][0].insert(Node(t[i], i));
}
else
{
tim[id][p[i][0] - 'A'][0].erase(tim[id][p[i][0] - 'A'][0].find(Node(t[i], i)));
tim[id][p[i][0] - 'A'][1].insert(Node(t[i], i));
}
if ( !tim[id][p[i][0] - 'A'][0].empty() )
{
++val[id].cntpro;
val[id].sumtime += (*tim[id][p[i][0] - 'A'][0].begin()).t;
int rk = lower_bound(seq[id][p[i][0] - 'A'].begin(), seq[id][p[i][0] - 'A'].end(), (*tim[id][p[i][0] - 'A'][0].begin())) - seq[id][p[i][0] - 'A'].begin();
val[id].sumtime += rk * 20;
}
if ( val[id].cntpro )
++n;
++bin[val[id]];
}
sort(d + 1, d + 1 + len);
sum = 0;
for ( int i = 1; i <= cnt; i ++ )
{
int pos = lower_bound(d + 1, d + 1 + len, val[i]) - d;
ans[i] += len - pos + 1;
if ( ans[i] )
++sum;
// cout << name[i] << ' ';
// printf("ans = %d\n", ans[i]);
}
printf("%d\n", sum);
for ( int i = 1; i <= cnt; i ++ )
if ( ans[i] )
cout << name[i] << ' ';
cout << endl;
return;
}
int main ()
{
scanf("%d", &T);
while ( T -- )
Work();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 55ms
memory: 321480kb
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: 65ms
memory: 321704kb
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: 51ms
memory: 321416kb
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: 43ms
memory: 321712kb
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: 197ms
memory: 321372kb
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: 150ms
memory: 321436kb
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 1 fhYPGC8W82NwJTQL 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 _Yej1PrINtydmOudwoO PezeyUurYoz7N...
result:
wrong answer the numbers are different in the case 3. (test case 3)