QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #634800 | #8230. Submissions | LateRegistration# | WA | 4ms | 9936kb | C++20 | 4.2kb | 2024-10-12 18:08:00 | 2024-10-12 18:08:01 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int n=0,f=1,ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
n=n*10+ch-'0';
ch=getchar();
}
return n*f;
}
unordered_map<string,int>ma;
vector<pair<int,int> >v[100005][26];
string mz[100005];
int cnt;
pair<int,int> fs[100005];
int pos[100005],pos2[100005];
bool kx[100005];
bool bi(int x,int y)
{
if(fs[x].first!=fs[y].first)return fs[x].first>fs[y].first;
return fs[x].second<fs[y].second;
}
int main()
{
int t,m,bh,tid,sj;
string str;
t=read();
for(int greg=1;greg<=t;greg++)
{
m=read();
ma.clear();
for(int i=1;i<=m;i++)
{
for(int j=0;j<26;j++)v[i][j].clear();
kx[i]=false;
fs[i]=make_pair(0,0);
}
cnt=0;
for(int i=1;i<=m;i++)
{
cin>>str;
if(!ma.count(str))ma[str]=++cnt,mz[cnt]=str;
bh=ma[str];
tid=getchar();
while(tid<'A'||tid>'Z')tid=getchar();
tid=tid-'A';
sj=read();
cin>>str;
int st=0;
if(str[0]=='a')st=1;
else st=0;
//printf("%d %d %d %d\n",bh,tid,sj,st);
v[bh][tid].push_back(make_pair(sj,st));
}
//printf("orz\n");
if(cnt==1)
{
cout<<mz[1]<<endl;
continue;
}
for(int i=1;i<=cnt;i++)
{
pos[i]=i;
for(int j=0;j<26;j++)
{
for(int k=0;k<v[i][j].size();k++)
{
if(v[i][j][k].second==1)
{
fs[i].first++;
fs[i].second+=k*20+v[i][j][k].first;
break;
}
}
}
//printf("%d %d %d\n",i,fs[i].first,fs[i].second);
}
sort(pos+1,pos+cnt+1,bi);
int yt=0;
for(int i=1;i<=cnt;i++)if(fs[pos[i]].first>=1)yt++;
int jp=min(35,(yt+9)/10);
for(int i=1;i<=cnt;i++)if(!bi(pos[jp],pos[i]))kx[pos[i]]=true;
for(int ii=1;ii<=jp;ii++)
{
int i=pos[ii];
int jp1=min(35,(yt-1+9)/10);
pair<int,int> minn=fs[i];
for(int j=0;j<26;j++)
{
pair<int,int> now=fs[i];
for(int k=0;k<v[i][j].size();k++)
{
if(v[i][j][k].second==1)
{
now.first--;
now.second-=k*20+v[i][j][k].first;
for(int l=k+1;l<v[i][j].size();l++)
{
if(v[i][j][k].second==1)
{
now.first++;
now.second+=l*20+v[i][j][l].first;
break;
}
}
break;
}
}
if(now.first<minn.first||(now.first==minn.first&&now.second>minn.second))minn=now;
}
//printf("%d %d %d\n",i,minn.first,minn.second);
if(minn.first==0&&jp1<jp)continue;
pair<int,int> yl=fs[i];
fs[i]=minn;
for(int j=1;j<=cnt;j++)pos2[j]=j;
sort(pos2+1,pos2+cnt+1,bi);
//for(int j=1;j<=cnt;j++)if(!bi(pos2[jp],pos2[j]))printf("%d ",pos2[j]),kx[pos2[j]]=true;
fs[i]=yl;
}
for(int ii=1;ii<=cnt;ii++)
{
if(ii<=jp)continue;
int i=pos[ii];
pair<int,int> maxn=fs[i];
int jp1=min(35,(yt+1+9)/10);
for(int j=0;j<26;j++)
{
if(v[i][j].empty())continue;
pair<int,int> now=fs[i];
for(int k=0;k<v[i][j].size();k++)
{
if(v[i][j][k].second==1)
{
now.first--;
now.second-=k*20+v[i][j][k].first;
break;
}
}
now.first++;
now.second+=v[i][j][0].first;
if(now.first>maxn.first||(now.first==maxn.first&&now.second<maxn.second))maxn=now;
}
//cout<<mz[i]<<" ";
//printf("%d %d\n",fs[i].first,fs[i].second);
//cout<<mz[i]<<" ";
//printf("%d %d\n",maxn.first,maxn.second);
if(maxn.first>fs[pos[jp]].first||(maxn.first==fs[pos[jp]].first&&maxn.second<=fs[pos[jp]].second))kx[i]=true;
if(fs[i].first==0&&maxn.first>0&&jp1>jp)
{
if(maxn.first>fs[pos[jp]].first||(maxn.first==fs[pos[jp1]].first&&maxn.second<=fs[pos[jp1]].second))kx[i]=true;
}
}
int jp1=min(35,(yt+1+9)/10);
int mfs=-1;
for(int i=1;i<=cnt;i++)
{
if(fs[i].first!=0)continue;
for(int j=0;j<26;j++)
{
for(int k=0;k<v[i][j].size();k++)
{
mfs=max(mfs,v[i][j][k].first+k*20);
}
}
}
if(mfs!=-1&&jp1>jp)
{
if(fs[pos[jp+1]].first>1||(fs[pos[jp+1]].first==1&&fs[pos[jp+1]].second<=mfs))
{
for(int k=1;k<=cnt;k++)if(!bi(pos[jp+1],pos[k]))kx[pos[k]]=true;
}
}
int ans=0;
for(int i=1;i<=cnt;i++)if(kx[i])ans++;
printf("%d\n",ans);
for(int i=1;i<=cnt;i++)if(kx[i])cout<<mz[i]<<" ";
cout<<endl;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 9936kb
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: -100
Wrong Answer
time: 4ms
memory: 7872kb
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:
1 jiangly_fan 1 conqueror_of_tourist
result:
wrong answer the numbers are different in the case 1. (test case 1)