QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #369835 | #8230. Submissions | liswt | WA | 68ms | 59156kb | C++14 | 4.0kb | 2024-03-28 18:28:22 | 2024-03-28 18:28:22 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int T;
int n,m;
int ac;
struct ti
{
int id,tid,tim,sta;//队伍id，题id，提交时间，是否ac
}o[N];//提交
struct team
{
string name;//队名
int id;//队伍id
int ac;//总ac数
int penty;//总罚时
int ac1[26];//第1个ac是第几次提交，0代表没有
int tim1[26];//第1个ac的时间
int ac2[26];//第2个ac是第几次提交，0代表没有
int tim2[26];//第2个ac的时间
int ti[26];//总提交次数
}a[N];
int b[N];//离散化id
int d[N][26];
bool operator==(const team&a,const team&b){return a.ac==b.ac&&a.penty==b.penty;}
bool operator>(const team&a,const team&b){return a.ac==b.ac?a.penty<b.penty:a.ac>b.ac;}
bool operator<(const team&a,const team&b){return a.ac==b.ac?a.penty>b.penty:a.ac<b.ac;}
bool cmp(const team&a,const team&b){return a.ac==b.ac?a.penty<b.penty:a.ac>b.ac;}
void solve()
{
set<int>ans;
map<string,int>id;
a[0].ac=-1;
cin>>m;//提交数量
n=0;//队伍数量
ac=0;//至少过1题的队伍数量
for(int i=1;i<=m;i++)
{
int t;
string c,p,s;
cin>>c>>p>>t>>s;
if(id[c]==0)
{
n++;
id[c]=n;
a[n].name=c;
a[n].id=n;
a[n].ac=0;
a[n].penty=0;
for(int j=0;j<26;j++)
{
a[n].ac1[j]=0;
a[n].tim1[j]=0;
a[n].ac2[j]=0;
a[n].tim2[j]=0;
a[n].ti[j]=0;
}
}
int u=id[c];
o[i].id=u;
o[i].tid=p[0]-'A';
o[i].tim=t;
o[i].sta=s[0]=='a'?1:0;
int v=o[i].tid;
a[u].ti[v]++;
if(o[i].sta)
{
if(a[u].ac1[v]==0)
{
a[u].ac1[v]=a[u].ti[v];
a[u].tim1[v]=(a[u].ti[v]-1)*20+t;
a[u].ac++;
a[u].penty+=a[u].tim1[v];
}
else if(a[u].ac2[v]==0)
{
a[u].ac2[v]=a[u].ti[v];
a[u].tim2[v]=(a[u].ti[v]-1)*20+t;
}
}
}
if(n==1)
{
if(a[1].ac)
cout<<1<<endl<<a[1].name<<endl;
else
cout<<0<<endl;
return;
}
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++)
{
// cout<<a[i].name<<" "<<a[i].ac<<" "<<a[i].penty<<endl;
// for(int j=0;j<26;j++)
// {
// cout<<char(j+'A')<<" ";
// cout<<a[i].ac1[j]<<" ";
// cout<<a[i].tim1[j]<<" ";
// cout<<a[i].ac2[j]<<" ";
// cout<<a[i].tim2[j]<<" ";
// cout<<a[i].ti[j]<<" ";
// cout<<endl;
// }
if(a[i].ac)ac++;
b[a[i].id]=i;
for(int j=0;j<26;j++)
{
d[i][j]=0;
}
}
int M=min((ac+9)/10,35);
for(int j=1;j<=M;j++)
{
ans.insert(a[j].id);
}
for(int j=M+1;j<=n;j++)
{
if(a[j]==a[j-1])ans.insert(a[j].id);
else break;
}
int over=0;
for(int i=1;i<=m;i++)
{
int k=b[o[i].id];
auto v=o[i].tid;
auto tmp=a[k];
d[k][v]++;
int acc=0;
if(!a[k].ac1[v])
{
if(a[k].ac==0)acc=1;
a[k].ac++;
a[k].penty+=(d[k][v]-1)*20+o[i].tim;
}
else
{
if(d[k][v]<a[k].tim1[v])
{
a[k].penty-=a[k].tim1[v];
a[k].penty+=(d[k][v]-1)*20+o[i].tim;
}
else if(d[k][v]==a[k].tim1[v])
{
if(a[k].ac2[v])
{
a[k].penty-=a[k].tim1[v];
a[k].penty+=a[k].tim2[v];
}
else
{
// cout<<"***"<<i<<endl;
if(a[k].ac==1)acc=-1;
a[k].ac--;
a[k].penty-=a[k].tim1[v];
}
}
else
{
continue;
}
}
int M=min((ac+acc+9)/10,35);
int used=0;
int re=0;
for(int j=1,cnt=1;cnt<=M;)
{
// cout<<i<<" "<<j<<" "<<k<<" "<<cnt<<" "<<M<<endl;
if(j==k){j++;continue;}
if(!used)
{
if(!(a[k]<a[j]))
{
used=1;
ans.insert(a[k].id);
cnt++;
re=-1;
continue;
}
}
ans.insert(a[j].id);
cnt++;
j++;
}
for(int j=M+re+1;j<=n;j++)
{
if(j>=40&&over==2)break;
if(j>=40)over=1;
if(a[j]==a[j-1])ans.insert(a[j].id);
else break;
}
if(over)over=2;
a[k]=tmp;
// cout<<i<<endl;
// cout<<ans.size()<<endl;
// for(auto x:ans)cout<<a[b[x]].name<<" ";
// cout<<endl;
}
cout<<ans.size()<<endl;
for(auto x:ans)cout<<a[b[x]].name<<" ";
cout<<endl;
}
int main()
{
cin.tie(0)->sync_with_stdio(false);
cout.tie(0)->sync_with_stdio(false);
cin>>T;
while(T--)
{
solve();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 8ms
memory: 59080kb
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: 3ms
memory: 59156kb
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: 4ms
memory: 59104kb
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: 3ms
memory: 59124kb
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
Wrong Answer
time: 68ms
memory: 59116kb
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 0 1 ftQVK8S_um22w 1 _bQBeFeDpYQhvZcLf9l3 0 0 1 gxYo_oCFn2J8aIben 1 _isnlUGK0ddI 1 BERcVjyCp 0 0 1 7njYOapSwvogA 0 1 y1w3KvxylfxwprRBYw 0 1 iPo0GDhIF 0 0 0 1 HsVWeBf6j 0 0 0 0 1 AIfIfX 1 EYT72BapastGY9a 0 0 1 Ua5BlM9OD 1 G_zQlC7Z27HdXIK0lCG 1...
result:
wrong answer Integer parameter [name=n] equals to 0, violates the range [1, 100000] (test case 5)