Hotpot

Sichuan hotpot is one of the most famous dishes around the world. People love its spicy taste.

There are $n$ tourists, numbered from $0$ to $(n-1)$ , sitting around a hotpot. There are $k$ types of ingredients for the hotpot in total and the $i$ -th tourist favors ingredient $a_i$ most. Initially, every tourist has a happiness value of $0$ and the pot is empty.

The tourists will perform $m$ moves one after another, where the $i$ -th (numbered from $0$ to $(m - 1)$ ) move is performed by tourist $(i \mod n)$ . When tourist $t$ moves:

If ingredient $a_t$ exists in the pot, he will eat them all and gain $1$ happiness value.
Otherwise, he will put one unit of ingredient $a_t$ into the pot. His happiness value remains unchanged.

Your task is to calculate the happiness value for each tourist after $m$ moves.

There are multiple test cases. The first line of the input contains an integer $T$ ( $1 \le T \le 10^3$ ) indicating the number of test cases. For each test case:

The first line contains three integers $n$ , $k$ and $m$ ( $1 \le n \le 10^5$ , $1 \le k \le 10^5$ , $1 \le m \le 10^9$ ) indicating the number of tourists, the number of types of ingredients and the number of moves.

The second line contains $n$ integers $a_0, a_1, \cdots, a_{n-1}$ ( $1 \le a_i \le k$ ) where $a_i$ indicates the favorite ingredient of tourist $i$ .

It's guaranteed that neither the sum of $n$ nor the sum of $k$ of all the test cases will exceed $2 \times 10^5$ .

For each test case output $n$ integers $h_0, h_1, \cdots, h_{n-1}$ in one line separated by a space, where $h_i$ indicates the happiness value of tourist $i$ after $m$ moves.

Please, DO NOT output extra spaces at the end of each line, or your answer might be considered incorrect!

#include<bits/stdc++.h> using namespace std; const int maxn=10005; int T,n,m,k,ans[maxn],a[maxn],f[maxn]; int main(){ for (scanf("%d",&T);T;--T){ scanf("%d%d%d",&n,&k,&m); memset(f,0,sizeof(f)); for (int i=0;i<n;++i) scanf("%d",&a[i]),ans[i]=0; int t=m/(2*n); for (int i=0;i<2*n;++i){ if (!f[a[i%n]]) f[a[i%n]]=1;else{ if (m%(2*n)-1>=i) {ans[i%n]++;} f[a[i%n]]=0,ans[i%n]+=t; } } for (int i=0;i<n;++i) printf("%d%c",ans[i],i<n-1?' ':'\n'); } return 0; }

详情