QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#344623#8230. SubmissionszzuqyWA 4ms15744kbC++145.5kb2024-03-04 20:33:292024-03-04 20:33:30

Judging History

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

  • [2024-05-20 23:50:57]
  • hack成功,自动添加数据
  • (/hack/623)
  • [2024-05-20 23:48:44]
  • hack成功,自动添加数据
  • (/hack/622)
  • [2024-03-04 20:33:30]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:15744kb
  • [2024-03-04 20:33:29]
  • 提交

answer

#include<bits/stdc++.h>
#define N 200009
using namespace std;
int a[N][26][4];//0 now;1 highest;2 lowest
unordered_map<string,int>mp;
string rmp[N];
int n,n2;
bool cmp(const pair<int,int> &a,const pair<int,int>&b){
	if(a.first>b.first)return 1;
	if(a.first<b.first)return 0;
	if(a.second<b.second)return 1;
	return 0;
}
struct mapstruct{
	bool operator()(const pair<int,int> &a,const pair<int,int>&b){
		return cmp(a,b);
	}
};
int calcgold(int n){
	return min((n+9)/10,35);
}
bool in[N];
int goldsize=0;
map<pair<int,int>,int,mapstruct>gold;
vector<int>gold2[N];
pair<int,int>line,line2;
void handle(){
	int x=calcgold(n2);
	int cnt=0;
	//assert(gold.size()<=x+1);
	for(auto i:gold){
		if(cnt<x)for(auto j:gold2[i.second])in[j]=1,cnt++; 
		else break;
		//cout<<cnt<<"?"<<x<<endl;
	}
}
void del(int x,pair<int,int>score){
	if(score.first>0)n2--;
	if(!cmp(line,score)){
		int id=gold[score];
		for(int i=0;i<gold2[id].size();i++){
			if(gold2[id][i]==x){
				swap(gold2[id][i],gold2[id][gold2[id].size()-1]);
				gold2[id].pop_back();
				break;
			}
		}
		if(gold2[id].size()==0)gold.erase(score);
	}
}
void add(int x,pair<int,int>score){
	if(score.first>0)n2++;
	//cout<<score.first<<" "<<score.second<<endl;
	if(!cmp(line,score)){
		if(gold[score]==0){
			gold[score]=++goldsize;
			gold2[goldsize].clear();
		}
		gold2[gold[score]].push_back(x);
	}
}
void query(int x,pair<int,int>normal,pair<int,int>score){
	del(x,normal);
	add(x,score);
	handle();
	del(x,score);
	add(x,normal);
}
void solve(){
	mp.clear();n=n2=0;line=make_pair(0,0);line2=make_pair(1000,0);
	gold.clear();goldsize=0;
	int m;cin>>m;
	while(m--){
		string s;char c;int t;string p;
		cin>>s>>c>>t>>p;
		if(mp[s]==0){
			mp[s]=++n;rmp[n]=s;
			for(int i=0;i<26;i++)a[n][i][0]=a[n][i][1]=a[n][i][2]=-1000000000;
		}
		int x=mp[s],id=c-'A';
		if(p=="accepted"){
			
			if(a[x][id][0]<0)a[x][id][0]=a[x][id][0]+1000000000+t,a[x][id][2]+=20;
			else a[x][id][2]=a[x][id][2]+1000000000+t;
			//cout<<x<<" "<<id<<" "<<a[x][id][2]<<endl; 
			if(a[x][id][1]<0)a[x][id][1]=t;
		}
		if(p=="rejected"){
			if(a[x][id][0]<0)a[x][id][0]+=20,a[x][id][3]=t;
			if(a[x][id][1]<0)a[x][id][1]=t;
			if(a[x][id][2]<0)a[x][id][2]+=20;
		}
	}
	for(int i=1;i<=n;i++){
		int c=0,p=0;
		for(int j=0;j<26;j++)if(a[i][j][0]>=0)c++,p+=a[i][j][0];
		if(gold[make_pair(c,p)]==0){
			gold[make_pair(c,p)]=++goldsize;
			gold2[goldsize].clear();
		}
		gold2[gold[make_pair(c,p)]].push_back(i);
		if(c>0)n2++;
		//cout<<rmp[i]<<" "<<c<<" "<<p<<endl;
	}
	int cnt=0;
	for(auto it:gold){
		
		cnt+=gold2[it.second].size();
		line=it.first; 
		if(cnt<calcgold(n2))line2=it.first;
		if(cnt>calcgold(n2))break;
	}
	while(1){
		auto it=gold.end();it--;
		if(cmp(line,(*it).first))gold.erase(it);
		else break;
	}
	handle();
	int id=0,what=0;
	for(int i=1;i<=n;i++){
		pair<int,int>best=make_pair(-1000,0),worst=make_pair(1000,0),normal=make_pair(0,0);
		for(int x=0;x<26;x++)if(a[i][x][0]>=0)normal.first++,normal.second+=a[i][x][0];
		int c=0,p=0;
		for(int x=0;x<26;x++){
			c=0;p=0;
			if(a[i][x][0]>=0)c--,p-=a[i][x][0];
			if(a[i][x][1]>=0)c++,p+=a[i][x][1];
			if(cmp(make_pair(c,p),best))best=make_pair(c,p);
		}
		best.first+=normal.first;best.second+=normal.second;
		for(int x=0;x<26;x++){
			c=0;p=0;
			if(a[i][x][0]>=0)c--,p-=a[i][x][0];
			if(a[i][x][2]>=0)c++,p+=a[i][x][2];
			if(cmp(worst,make_pair(c,p)))worst=make_pair(c,p);
		}
		worst.first+=normal.first;worst.second+=normal.second;
		int tmp=0;
		for(int x=0;x<26;x++){
			if(a[i][x][0]<0&&a[i][x][0]>-1000000000)tmp=max(tmp,a[i][x][0]-20+1000000000+a[i][x][3]+1);
		}
		//cout<<normal.first<<"-"<<normal.second<<" ";
		//cout<<best.first<<"-"<<best.second<<" ";
		//cout<<worst.first<<"-"<<worst.second<<" ";
		
		if(normal!=best){
			if(normal.first==0&&n2%10==0)query(i,normal,best);
			else if(cmp(best,line2))in[i]=1;
			else if(!cmp(line,best))query(i,normal,best);
		}
		if(normal!=worst&&!cmp(line,normal))query(i,normal,worst);
		if(tmp>what)id=i,what=tmp;
	}
	if(id)query(id,make_pair(0,0),make_pair(1,what));
	int ans=0;
	for(int i=1;i<=n;i++)if(in[i])ans++;
	cout<<ans<<endl;
	for(int i=1;i<=n;i++)if(in[i])cout<<rmp[i]<<" ";cout<<endl;
	for(int i=1;i<=n;i++){
		rmp[i]="";in[i]=0;
		for(int j=0;j<26;j++)a[i][j][0]=a[i][j][1]=a[i][j][2]=0;
	}
}
int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	int t;cin>>t;
	while(t--)solve(); 
	return 0;
}
/*
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 accepted
ImYourFan I 257 accepted
ImYourFan Y 257 accepted
AllWayTheNorth T 264 accepted
XuejunXinyoudui1 J 294 accepted
LetItRot I 299 accepted
LetItRot I 299 rejected

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

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 1 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 accepted
G G 2 accepted
H H 2 accepted
I I 2 accepted
J J 2 rejected
K K 2 rejected

*/

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 15060kb

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: 4ms
memory: 14928kb

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: 15744kb

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: -100
Wrong Answer
time: 0ms
memory: 15280kb

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

result:

wrong answer the numbers are different in the case 2. (test case 2)