NWERC 2019 A

2020-12-07 21:59:08 sgxsgx

A. Average Rank

The National Weekly Escape Room Challenge (NWERC) is a long-running competition held in Eindhoven. Every week a new escape room is presented, and anyone who completes it in their first attempt gains one point.

At the end of each week, competitors are ranked by the total number of points accumulated so far, highest first. In the case of a tie, they share the same rank. In other words, the rank of a competitor is one more than the number of people with a strictly larger number of points.

In total there have been \(n\) participants in the contest, and the contest has been going for w weeks. For each week you are given a list of the competitors that gained a point that week. Your task is to calculate the average rank during the w-week competition for each competitor.
The figure illustrates the score progression in the third sample.

Input
The input consists of:

One line with two integers \(n\) and \(w\) (\(1≤n,w≤3⋅10^5\)), the number of competitors and the number of weeks. The competitors are numbered from \(1\) to \(n\).
\(w\) lines (one for each week), each containing an integer \(k\) (\(0≤k≤n\)) followed by \(k\) distinct integers \(c_1,…,c_k\) (\(1≤c_i≤n\) for all \(i\)), indicating that the \(k\) competitors \(c_1,…,c_k\) each gained a point that week.
The total number of points awarded is at most 1 million.

Output
Output \(n\) lines, the ith of which contains the average rank of the \(ith\) competitor during the \(w\)-week competition. Your answers should have an absolute or relative error of at most \(10^−6\).

Code

#include<bits/stdc++.h>
#define _(d) while(d(isdigit(ch=getchar())))
#define rep(i,a,b) for(int i=a;i<=b;i++)
template<class T>void g(T&t){T x,f=1;char ch;_(!)ch=='-'?f=-1:f;x=ch-48;_()x=x*10+ch-48;t=f*x;}
using namespace std;
const int N = 1e6 + 4;
typedef long long ll;
ll n, w, now[N], pre[N], cnt[N], p[N], sum[N];
int main(){
g(n), g(w);
cnt = n;
rep( i, 0, n ) sum[i] = w, p[i] = 1;
rep( i, 1, w ){
int Len; g(Len);
while( Len-- ){
int x; g(x);
sum[ x ] += now[ p[x] ] - pre[ x ];
now[ p[x] ] += ( w - i + 1 );
cnt[ p[x] ] --;
p[ x ] ++;
sum[ x ] -= cnt[ p[x] ] * ( w - i + 1 );
pre[ x ] = now[ p[x] ];
cnt[ p[x] ]++;
}
}
rep( i, 1, n ){
sum[i] += now[ p[i] ] - pre[i];
printf("%.11lf\n",1.0 * sum[i] / ( 1.0 * w ));
}
return 0;
}

https://www.cnblogs.com/sgxloveyy/p/14099960.html