Repovive
  • Dashboard
  • Ranking
  • Submissions
  • Discussion
  1. Contests
  2. Weekly Challenge 1: Approximation
  3. W1D3A

My submissions

/
/
/
/

Announcements

My submissions

/
/
/
/

Announcements

Solve
Author

W1D3A. Almost Assignment

1 pts·1s·256 MB

Constraints

Input

Output

Samples

Input
1
5
10 8 7 6 5
9 1 1 1 1
8 7 20 3 2
7 6 5 18 4
6 5 4 3 16
Explanation
Output
1 2 3 4 5

You are given nnn workers and nnn jobs.

If worker iii is assigned to job jjj, you gain profit ai,ja_{i,j}ai,j​.

You must assign each worker to exactly one job, and each job to exactly one worker. In other words, you must choose a permutation p1,p2,…,pnp_1,p_2,\ldots,p_np1​,p2​,…,pn​, where worker iii is assigned to job pip_ipi​.

The score of an assignment is:

∑i=1nai,pi\sum_{i=1}^{n} a_{i,p_i}∑i=1n​ai,pi​​

Let OPTOPTOPT be the maximum possible score of an assignment.

You do not need to find an optimal assignment. You only need to output any assignment whose score is at least half of OPTOPTOPT.

In other words, if the score of your assignment is SSS, your output is accepted if 2×S≥OPT2 \times S \ge OPT2×S≥OPT.

  • 1≤t≤31 \le t \le 31≤t≤3
  • 1≤n≤9001 \le n \le 9001≤n≤900
  • The sum of n2n^2n2 over all test cases is at most 900000900000900000
  • 1≤ai,j≤1091 \le a_{i,j} \le 10^91≤ai,j​≤109

The input is given in the following format:

ttt na1,1a1,2⋯a1,na2,1a2,2⋯a2,n⋮an,1an,2⋯an,n}×t\left. \begin{array}{l} n \\ a_{1,1} \quad a_{1,2} \quad \cdots \quad a_{1,n} \\ a_{2,1} \quad a_{2,2} \quad \cdots \quad a_{2,n} \\ \vdots \\ a_{n,1} \quad a_{n,2} \quad \cdots \quad a_{n,n} \end{array} \right\} \times tna1,1​a1,2​⋯a1,n​a2,1​a2,2​⋯a2,n​⋮an,1​an,2​⋯an,n​​⎭⎬⎫​×t

For each test case, output a permutation p1,p2,…,pnp_1,p_2,\ldots,p_np1​,p2​,…,pn​.

This means each integer from 111 to nnn must appear exactly once. Worker iii will be assigned to job pip_ipi​.

If the score of your assignment is SSS, it must satisfy 2×S≥OPT2 \times S \ge OPT2×S≥OPT.

The output format is:

p1p2⋯pn}×t\left. \begin{array}{l} p_1 \quad p_2 \quad \cdots \quad p_n \end{array} \right\} \times tp1​p2​⋯pn​​}×t

The shown assignment gives jobs 1,2,3,4,51,2,3,4,51,2,3,4,5 to workers 1,2,3,4,51,2,3,4,51,2,3,4,5 respectively.

Its score is 10+1+20+18+16=6510+1+20+18+16=6510+1+20+18+16=65.

This is not optimal: assigning jobs 2,1,3,4,52,1,3,4,52,1,3,4,5 gives score 8+9+20+18+16=718+9+20+18+16=718+9+20+18+16=71. Still, the shown assignment is accepted because 2×65≥712 \times 65 \ge 712×65≥71.