题解：P15081 [ICPC 2024 Chengdu R] Grand Prix of Ballance

huangboning · 2026-01-26 20:34:44 · 题解

模拟，没别的。

用 map 记录是否完赛，用 s 记录每个人积分之和。设当前关卡为 t，只处理 y=t 且 mp_x=0 的询问。大力在 vector 插入关卡完成顺序，一关结束时先处理积分。

记得最后处理一遍最后一关。

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node{
    int s,id;
}s[100010];
bool cmp(node a,node b){
    if(a.s!=b.s)return a.s>b.s;
    return a.id<b.id;
}
int T,n,m,q,t;
vector<int>v;
map<int,bool>mp;
signed main()
{
    ios::sync_with_stdio(0);
    cin>>T;
    while(T--){
        cin>>n>>m>>q;t=0;v.clear();mp.clear();
        for(int i=1;i<=m;i++)s[i].s=0,s[i].id=i;
        for(int i=1;i<=q;i++){
            int op,x,y;
            cin>>op>>x;
            if(op==1){
                int cnt=m;
                for(int i:v)s[i].s+=cnt--;
                v.clear();mp.clear();t=x;
            }
            else if(op==2){
                cin>>y;if(y!=t||mp[x])continue;
                mp[x]=1;v.push_back(x);
            }
            else{
                cin>>y;if(y!=t||mp[x])continue;
                mp[x]=1;
            }
        }
        int cnt=m;
        for(int i:v)s[i].s+=cnt--;
        v.clear();mp.clear();
        sort(s+1,s+m+1,cmp);
        for(int i=1;i<=m;i++)cout<<s[i].id<<" "<<s[i].s<<"\n";
    }
}