QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #364898 | #8230. Submissions | ucup-team1525# | RE | 1ms | 4084kb | C++14 | 7.1kb | 2024-03-24 17:12:23 | 2024-03-24 17:12:24 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
void solve()
{
map<string,int> name2id;
vector<string> id2name;
vector<vector<pair<int,int> > > mp[26];
vector<pair<int,int> > tmp;
tmp.clear();
string name,prob,stat;
int ti,n;
int cnt=0;
cin>>n;
for (int i=1;i<=n;++i)
{
cin>>name>>prob>>ti>>stat;
if (name2id.find(name)==name2id.end())
{
name2id[name]=cnt++;
id2name.push_back(name);
for (int j=0;j<26;++j)
mp[j].push_back(tmp);
}
int id=name2id[name],sta=stat[0]=='a'?1:0;
mp[prob[0]-'A'][id].push_back({sta,ti});
}
vector<pair<int,int> > grade,gradeup,gradelow;
int n0cnt=0;
int subac[26],nowt[26];
int mxex=-1;
// int _golden=min(35,(cnt-1)/10+1);
for (int i=0;i<cnt;++i)
{
int p=0,q=0;
for (int j=0;j<26;++j)
{
subac[j]=0;
for (int k=0;k<(int)mp[j][i].size();++k)
if (mp[j][i][k].first==1)
{
++p;
q+=mp[j][i][k].second+k*20;
nowt[j]=mp[j][i][k].second+k*20;
break;
}
for (int k=0;k<(int)mp[j][i].size();++k)
if (mp[j][i][k].first==1)
++subac[j];
// cout<<subac[j];
}
// cout<<endl;
grade.push_back({p,q});
int pu=p,qu=q;
int pl=p,ql=q;
for (int j=0;j<26;++j)
if (!mp[j][i].empty())
{
// cout<<j<<' '<<subac[j]<<';';
if (subac[j]==0)
{
int _p=p+1,_q=q+mp[j][i][0].second;
if (_p>pu||_q<qu)
{
pu=_p;
qu=_q;
}
}
if (subac[j]==1)
{
int _p=p-1,_q=q-nowt[j];
if (_p<ql||_q>ql)
{
pl=_p;
ql=_q;
}
_p=p,_q=q-nowt[j]+mp[j][i][0].second;
if (_p>pu||(_p==pu&&_q<qu))
{
pu=_p;
qu=_q;
}
}
if (subac[j]>=2)
{
int _p=p,_q=q-nowt[j];
int accnt=0;
for (int k=0;k<(int)mp[j][i].size();++k)
if (mp[j][i][k].first==1)
{
++accnt;
if (accnt==2)
{
_q+=mp[j][i][k].second+k*20;
break;
}
}
if (_p<ql||(_p==pl&&_q>ql))
{
pl=_p;
ql=_q;
}
_p=p,_q=q-nowt[j]+mp[j][i][0].first;
if (_p>pu||(_p==pu&&_q<qu))
{
pu=_p;
qu=_q;
}
}
}
gradeup.push_back({pu,qu});
gradelow.push_back({pl,ql});
if (p!=0)
{
++n0cnt;
}
else
{
for (int j=0;j<26;++j)
for (int k=0;k<(int)mp[j][i].size();++k)
mxex=max(mxex,mp[j][i][k].second);
}
// cout<<endl;
}
int golden=min(35,(n0cnt-1)/10+1);
int __golden=min(35,max(0,(n0cnt-2))/10+1);
int _golden=min(35,min(n0cnt,(cnt-1))/10+1);
// cout<<golden<<' '<<_golden<<' '<<mxex<<endl;
vector<int> rk;
for (int i=0;i<cnt;++i)
rk.push_back(i);
sort(rk.begin(),rk.end(),[&](int x,int y){return grade[x].first==grade[y].first?grade[x].second<grade[x].second:grade[x].first>grade[y].first;});
int pl=grade[0].first,ql=grade[0].second;
vector<int> ans;
for (int i=0;i<golden;++i)
if ((gradelow[rk[i]].first==pl&&gradelow[rk[i]].second>ql)||(gradelow[rk[i]].first<pl))
{
pl=gradelow[rk[i]].first;
ql=gradelow[rk[i]].second;
}
// for (int i=0;i<cnt;++i)
// printf("%s ",id2name[rk[i]].c_str());
int oldpl=pl;
// cout<<"pl ql:"<<pl<<' '<<ql<<endl;
if ((grade[rk[golden]].first==pl&&grade[rk[golden]].second<ql)||(grade[rk[golden]].first>pl))
{
pl=grade[rk[golden]].first;
ql=grade[rk[golden]].second;
}
for (int i=0;i<golden;++i)
ans.push_back(rk[i]);
// cout<<"pl ql:"<<pl<<' '<<ql<<endl;
for (int i=golden;i<cnt;++i)
{
int x=rk[i];
if (((gradeup[x].first>grade[rk[golden-1]].first)||(gradeup[x].first==grade[rk[golden-1]].first&&gradeup[x].second<=grade[rk[golden-1]].second))||
(((grade[x].first>pl)||(grade[x].first==pl&&grade[x].second<=ql))&&(oldpl!=0||__golden==golden))||
((grade[x].first==0)&&(gradeup[x].first!=0)&&((gradeup[x].first>grade[rk[_golden-1]].first)||(gradeup[x].first==grade[rk[_golden-1]].first&&gradeup[x].second<=grade[rk[_golden-1]].second)))||
(mxex!=-1&&grade[rk[_golden-1]].first==1&&grade[x].first==1&&grade[x].second<=min(grade[rk[_golden-1]].second,mxex))||
(mxex!=-1&&grade[rk[_golden-1]].first!=1&&((grade[x].first>grade[rk[_golden-1]].first)||(grade[x].first==grade[rk[_golden-1]].first&&grade[x].second<=grade[rk[_golden-1]].second))))
{
// cout<<id2name[x]<<':';
// cout<<(bool)((gradeup[x].first>grade[rk[golden-1]].first)||(gradeup[x].first==grade[rk[golden-1]].first&&gradeup[x].second<=grade[rk[golden-1]].second));
// cout<<(bool)((grade[x].first>pl)||(grade[x].first==pl&&grade[x].second<=ql)&&(oldpl!=0||__golden==golden));
// cout<<(bool)((grade[x].first==0)&&(gradeup[x].first!=0)&&((gradeup[x].first>grade[rk[_golden-1]].first)||(gradeup[x].first==grade[rk[_golden-1]].first&&gradeup[x].second<=grade[rk[_golden-1]].second)));
// cout<<(bool)(mxex!=-1&&grade[rk[_golden-1]].first==1&&grade[x].first==1&&grade[x].second<=min(grade[rk[_golden-1]].second,mxex));
// cout<<(bool)(mxex!=-1&&(grade[rk[_golden-1]].first!=1)&&((grade[x].first>grade[rk[_golden-1]].first)||(grade[x].first==grade[rk[_golden-1]].first&&grade[x].second<=grade[rk[_golden-1]].second)))<<endl;
// cout<<(grade[rk[_golden-1]].first)<<endl;
ans.push_back(x);
}
}
// for (int i=0;i<cnt;++i)
// {
// printf("%s:",id2name[i].c_str());
// printf("%d %d; %d %d; %d %d\n",grade[i].first,grade[i].second,gradeup[i].first,gradeup[i].second,gradelow[i].first,gradelow[i].second);
// }
printf("%d\n",ans.size());
for (int x:ans)
printf("%s ",id2name[x].c_str());
puts("");
}
int main()
{
int t;
cin>>t;
while (t--)
solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3812kb
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 XuejunXinyoudui1 LetItRot ImYourFan
result:
ok 2 test cases ok. (2 test cases)
Test #2:
score: 0
Accepted
time: 0ms
memory: 4080kb
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: 0ms
memory: 3848kb
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: 4084kb
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: -100
Runtime Error
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