Phoenix and Towers solution codeforces – Phoenix has nn blocks of height h1,h2,…,hnh1,h2,…,hn , 2021

Phoenix and Towers solution codeforces

Phoenix and Towers solution codeforces Phoenix and Towers solution codeforces Phoenix and Towers solution codeforces

Phoenix has nn blocks of height h1,h2,,hnh1,h2,…,hn, and all hihi don’t exceed some value xx. He plans to stack all nn blocks into mm separate towers. The height of a tower is simply the sum of the heights of its blocks. For the towers to look beautiful, no two towers may have a height difference of strictly more than xx.

Please help Phoenix build mm towers that look beautiful. Each tower must have at least one block and all blocks must be used.

Phoenix and Towers solution codeforces Phoenix and Towers solution codeforces Phoenix and Towers solution codeforces

Input   Phoenix and Towers solution codeforces

The input consists of multiple test cases. The first line contains an integer tt (1t10001≤t≤1000) — the number of test cases.

The first line of each test case contains three integers nnmm, and xx (1mn1051≤m≤n≤1051x1041≤x≤104) — the number of blocks, the number of towers to build, and the maximum acceptable height difference of any two towers, respectively.

The second line of each test case contains nn space-separated integers (1hix1≤hi≤x) — the heights of the blocks.

It is guaranteed that the sum of nn over all the test cases will not exceed 105105.

Phoenix and Towers solution codeforces Phoenix and Towers solution codeforces Phoenix and Towers solution codeforces

Output   Phoenix and Towers solution codeforces

For each test case, if Phoenix cannot build mm towers that look beautiful, print NO. Otherwise, print YES, followed by nn integers y1,y2,,yny1,y2,…,yn, where yiyi (1yim1≤yi≤m) is the index of the tower that the ii-th block is placed in.

If there are multiple solutions, print any of them.

Example   Phoenix and Towers solution codeforces
Phoenix and Towers solution codeforces Phoenix and Towers solution codeforces Phoenix and Towers solution codeforces

input

Copy
2
5 2 3
1 2 3 1 2
4 3 3
1 1 2 3


output Phoenix and Towers solution codeforces Phoenix and Towers solution codeforces Phoenix and Towers solution codeforces

Copy
YES
1 1 1 2 2
YES
1 2 2 3
Note Phoenix and Towers solution codeforces Phoenix and Towers solution codeforces Phoenix and Towers solution codeforces

In the first test case, the first tower has height 1+2+3=61+2+3=6 and the second tower has height 1+2=31+2=3. Their difference is 63=36−3=3 which doesn’t exceed x=3x=3, so the towers are beautiful.

In the second test case, the first tower has height 11, the second tower has height 1+2=31+2=3, and the third tower has height 33. The maximum height difference of any two towers is 31=23−1=2 which doesn’t exceed x=3x=3, so the towers are beautiful.

PYTHON

Phoenix and Towers solution codeforces Phoenix and Towers solution codeforces Phoenix and Towers solution codeforces

for _ in range(int(input())):
n,m,x=map(int,input().split())
a=list(map(int,input().split()))
order=sorted(range(n),key=lambda i:-a[i])

ans=[0]*n
cur=0
for i in order:
ans[i]=cur+1
cur=(cur+1)%m
print("YES")
print(*ans)

C++

#include<bits/stdc++.h>
using namespace std;
int N,M,x; int a[10010];
int T;

int main() {
cin>>T;
for(;T;T--) {
cin>>N>>M>>x;set<pair<int,int> >q;
cout<<"YES"<<endl;
for(int i=0;i<M;i++) q.insert({0,i+1});
for(int i=0;i<N;i++) {
int a;cin>>a;
pair<int,int>t=*q.begin();q.erase(t); cout<<t.second<<' ';
q.insert({t.first+a,t.second});
}
cout<<endl;
}
}

JAVA 11

Phoenix and Towers solution codeforces Phoenix and Towers solution codeforces Phoenix and Towers solution codeforces

import java.io.*;
import java.util.*;

import static java.lang.Math.abs;

public class TP {

// constants
static final int MOD = (int) (1e9 + 7);
static final int IMAX = 0x7fffffff;
static final int IMIN = 0x80000000;
static final long LMAX = 0x7fffffffffffffffL;
static final long LMIN = -0x8000000000000000L;
public static PrintWriter out;

public static void main(String[] args) throws IOException {
long s = System.currentTimeMillis();
out = new PrintWriter(System.out);
// out = new PrintWriter(new BufferedWriter(new FileWriter("whereami.out")));
pre();
int t = 1;
t = ni();
int T = 1;
while (t-- > 0) {
solve();
}
out.flush();
tr(System.currentTimeMillis() - s + "ms");
}

private static void pre() {
}

private static void solve() {
int n = ni(), m = ni(), x = ni();
int[] a = na(n);
PriorityQueue<int[]> pd = new PriorityQueue<>(Comparator.comparingInt(g -> g[0]));
for (int i = 0; i < m; i++) pd.add(new int[]{0, i + 1});
out.println("YES");
for (int i = 0; i < n; i++) {
int[] pair = pd.poll();
out.print(pair[1] + " ");
}
out.println();
}

//input
private static int ni() {
return in.nextInt();
}

private static String ns() {
return in.next();
}

private static int[] na(int n) {
int[] a = new int[n];
for (int i = 0; i < n; i++) a[i] = ni();
return a;
}

private static long[] nal(int n) {
long[] a = new long[n];
for (int i = 0; i < n; i++) a[i] = nl();
return a;
}

private static long nl() {
return in.nextLong();
}

private float nf() {
return (float) in.nextDouble();
}

private static double nd() {
return in.nextDouble();
}

private static void print(int[] a) {
for (int x : a) out.print(x + " ");
out.println();
}

private static void print(long[] a) {
for (long x : a) out.print(x + " ");
out.println();
}

// array util
static void reverse(int[] a) {
for (int i = 0, n = a.length, half = n / 2; i < half; ++i) {
int swap = a[i];
a[i] = a[n - i - 1];
a[n - i - 1] = swap;
}
}

static void reverse(long[] a) {
for (int i = 0, n = a.length, half = n / 2; i < half; ++i) {
long swap = a[i];
a[i] = a[n - i - 1];
a[n - i - 1] = swap;
}
}

static void reverse(char[] a) {
for (int i = 0, n = a.length, half = n / 2; i < half; ++i) {
char swap = a[i];
a[i] = a[n - i - 1];
a[n - i - 1] = swap;
}
}

static int[] copy(int[] a) {
int[] ans = new int[a.length];
for (int i = 0; i < a.length; ++i) ans[i] = a[i];
return ans;
}

static long[] copy(long[] a) {
long[] ans = new long[a.length];
for (int i = 0; i < a.length; ++i) ans[i] = a[i];
return ans;
}

static char[] copy(char[] a) {
char[] ans = new char[a.length];
for (int i = 0; i < a.length; ++i) ans[i] = a[i];
return ans;
}

// math util

static int min(int... x) {
if (x.length == 1) return x[0];
if (x.length == 2) return Math.min(x[0], x[1]);
if (x.length == 3) return Math.min(x[0], Math.min(x[1], x[2]));
int min = x[0];
for (int i = 1; i < x.length; ++i) if (x[i] < min) min = x[i];
return min;
}

static long min(long... x) {
if (x.length == 1) return x[0];
if (x.length == 2) return Math.min(x[0], x[1]);
if (x.length == 3) return Math.min(x[0], Math.min(x[1], x[2]));
long min = x[0];
for (int i = 1; i < x.length; ++i) if (x[i] < min) min = x[i];
return min;
}

static int max(int... x) {
if (x.length == 1) return x[0];
if (x.length == 2) return Math.max(x[0], x[1]);
if (x.length == 3) return Math.max(x[0], Math.max(x[1], x[2]));
return Arrays.stream(x).max().getAsInt();
}

static long max(long... x) {
if (x.length == 1) return x[0];
if (x.length == 2) return Math.max(x[0], x[1]);
if (x.length == 3) return Math.max(x[0], Math.max(x[1], x[2]));
long max = x[0];
for (int i = 1; i < x.length; ++i) if (x[i] > max) max = x[i];
return max;
}

static int pow(int a, int b) {
if (a == 0) return 0;
int ans = 1;
while (b > 0) {
if ((b & 1) > 0) ans *= a;
a *= a;
b >>= 1;
}
return ans;
}

static long pow(long a, int b) {
if (a == 0) return 0;
long ans = 1;
while (b > 0) {
if ((b & 1) > 0) ans *= a;
a *= a;
b >>= 1;
}
return ans;
}

static int power(int x, int y, int p) {
int res = 1;
x = x % p;
while (y > 0) {
if (y % 2 == 1)
res = (res * x) % p;
y = y >> 1;
x = (x * x) % p;
}
return res;
}

static int modInverse(int n, int p) {
return power(n, p - 2, p);
}

static int nCrModPFermat(int n, int r, int p) {
if (n < r)
return 0;
if (r == 0)
return 1;
int[] fac = new int[n + 1];
fac[0] = 1;
for (int i = 1; i <= n; i++)
fac[i] = fac[i - 1] * i % p;
return (fac[n] * modInverse(fac[r], p) % p * modInverse(fac[n - r], p) % p) % p;
}

static boolean isPrime(long n) {
for (long i = 2; i * i <= n; i++) if (n % i == 0) return false;
return true;
}

public static long gcd(long a, long b) {
while (b != 0) {
a %= b;
long t = a;
a = b;
b = t;
}
return a;
}

private static boolean sorted(int[] a) {
for (int i = 0; i < a.length - 1; i++) {
if (a[i] > a[i + 1]) return false;
}
return true;
}

private static boolean sorted(long[] a) {
for (int i = 0; i < a.length - 1; i++) {
if (a[i] > a[i + 1]) return false;
}
return true;
}

private static boolean sorted(char[] a) {
for (int i = 0; i < a.length - 1; i++) {
if (a[i] > a[i + 1]) return false;
}
return true;
}

public static int lowerBound(int[] a, int v) {
int low = -1, high = a.length;
while (high - low > 1) {
int h = high + low >>> 1;
if (a[h] >= v) {
high = h;
} else {
low = h;
}
}
return high;
}

public static int[] facs(int n, int[] primes) {
int[] ret = new int[9];
int rp = 0;
for (int p : primes) {
if (p * p > n) break;
int i;
i = 0;
while (n % p == 0) {
n /= p;
i++;
}
if (i > 0) ret[rp++] = p;
}
if (n != 1) ret[rp++] = n;
return Arrays.copyOf(ret, rp);
}

public static int[] sieveEratosthenes(int n) {
if (n <= 32) {
int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
for (int i = 0; i < primes.length; i++) {
if (n < primes[i]) {
return Arrays.copyOf(primes, i);
}
}
return primes;
}

int u = n + 32;
double lu = Math.log(u);
int[] ret = new int[(int) (u / lu + u / lu / lu * 1.5)];
ret[0] = 2;
int pos = 1;

int[] isnp = new int[(n + 1) / 32 / 2 + 1];
int sup = (n + 1) / 32 / 2 + 1;

int[] tprimes = {3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
for (int tp : tprimes) {
ret[pos++] = tp;
int[] ptn = new int[tp];
for (int i = (tp - 3) / 2; i < tp << 5; i += tp) ptn[i >> 5] |= 1 << (i & 31);
for (int j = 0; j < sup; j += tp) {
for (int i = 0; i < tp && i + j < sup; i++) {
isnp[j + i] |= ptn[i];
}
}
}

// 3,5,7
// 2x+3=n
int[] magic = {
0, 1, 23, 2, 29, 24, 19, 3, 30, 27, 25, 11, 20, 8, 4, 13, 31, 22, 28, 18, 26, 10, 7, 12, 21,
17, 9, 6, 16, 5, 15, 14
};
int h = n / 2;
for (int i = 0; i < sup; i++) {
for (int j = ~isnp[i]; j != 0; j &= j - 1) {
int pp = i << 5 | magic[(j & -j) * 0x076be629 >>> 27];
int p = 2 * pp + 3;
if (p > n) break;
ret[pos++] = p;
if ((long) p * p > n) continue;
for (int q = (p * p - 3) / 2; q <= h; q += p) isnp[q >> 5] |= 1 << q;
}
}

return Arrays.copyOf(ret, pos);
}

private static int[][] uniqCount(int[] a) {
int n = a.length;
int p = 0;
int[][] b = new int[n][];
for (int i = 0; i < n; i++) {
if (i == 0 || a[i] != a[i - 1]) b[p++] = new int[]{a[i], 0};
b[p - 1][1]++;
}
return Arrays.copyOf(b, p);
}

private static long lcm(long a, long b) {
return a * b / gcd(a, b);
}

public static int[][] enumPrimesAndLPF(int n) {
int[] lpf = new int[n + 1];
double lu = Math.log(n + 32);

int tot = 0;
int[] primes = new int[(int) ((n + 32) / lu + (n + 32) / lu / lu * 1.5)];

for (int i = 2; i <= n; i++) {
lpf[i] = i;
}

for (int p = 2, tmp; p <= n; p++) {
if (lpf[p] == p) {
primes[tot++] = p;
}
for (int i = 0; i < tot && primes[i] <= lpf[p] && (tmp = primes[i] * p) <= n; i++) {
lpf[tmp] = primes[i];
}
}

return new int[][]{Arrays.copyOf(primes, tot), lpf};
}

public static int[] enumPrimes(int n) {
int[] lpf = new int[n + 1];
double lu = Math.log(n + 32);

int tot = 0;
int[] primes = new int[(int) ((n + 32) / lu + (n + 32) / lu / lu * 1.5)];

for (int i = 2; i <= n; i++) {
lpf[i] = i;
}

for (int p = 2, tmp; p <= n; p++) {
if (lpf[p] == p) {
primes[tot++] = p;
}
for (int i = 0; i < tot && primes[i] <= lpf[p] && (tmp = primes[i] * p) <= n; i++) {
lpf[tmp] = primes[i];
}
}

return Arrays.copyOf(primes, tot);
}

static boolean isPrime(int n) {
for (int i = 2; i * i <= n; i++) if (n % i == 0) return false;
return true;
}

//debug
private static final boolean oj = System.getProperty("ONLINE_JUDGE") != null;

private static void tr(Object... o) {
if (!oj) System.out.println(Arrays.deepToString(o));
}

StringTokenizer st;

}

String next() {
while (st == null || !st.hasMoreElements()) {
try {
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}

int nextInt() {
return Integer.parseInt(next());
}

long nextLong() {
return Long.parseLong(next());
}

double nextDouble() {
return Double.parseDouble(next());
}
}

}

.NET Core C#

Phoenix and Towers solution codeforces Phoenix and Towers solution codeforces Phoenix and Towers solution codeforces

using System;
using System.Collections.Generic;
using System.Diagnostics.CodeAnalysis;
using System.Globalization;
using System.IO;
using System.Text;

namespace Hacking
{
#if ONLINE_JUDGE

#else
//using Library;
#endif

public class Algo
{
private StreamWriter _w;

{
_w = w;
_r = r;
}

public void Run()
{
int t = _r.I();

for (int i = 1; i <= t; i++)
{
Solve();
}
}

private void Solve()
{
int n = _r.I();
int m = _r.I();
int x = _r.I();

int[] hh = _r.II(n);

SortedQueue<int, Tower> q = new SortedQueue<int, Tower>();
for(int i=0;i<m;i++)
{
var t = new Tower { Index = i, Height = 0 };
q.Enqueue(t);
}

Item[] items = new Item[n];
for (int i = 0; i < n; i++)
items[i] = new Item { Index = i, Value = hh[i] };
Array.Sort(items);
Array.Reverse(items);

for(int i=0; i<n;i++)
{
var t = q.Dequeue();
var item = items[i];

t.Height += item.Value;
item.TargetIndex = t.Index;

q.Enqueue(t);
}

if(q.Worst - q.Best > x)
{
_w.WriteYESNOLine(false);
return;
}

_w.WriteYESNOLine(true);

int[] tt = new int[n];
foreach (var item in items)
tt[item.Index] = item.TargetIndex+1;

_w.WriteNums(tt);
}

class Tower : IHasComparableKey<int>
{
public int Index;
public int Height;

public override string ToString() => $"{Height} @ {Index}"; public int GetKey() => Height; } class Item : IComparable<Item> { public int Index; public int TargetIndex; public int Value; public override string ToString() =>$"{Value} @ {Index} -> {TargetIndex}";

public int CompareTo([AllowNull] Item other)
{
return Value.CompareTo(other.Value);
}
}
}

public interface IHasComparableKey<TSize> where TSize : struct
{
TSize GetKey();
}

public sealed class SortedQueue<TKey, TValue>
where TKey : struct
where TValue : IHasComparableKey<TKey>
{

public SortedQueue()
{
_data = new Dictionary<TKey, List<TValue>>();
_keys = new SortedSet<TKey>();
}

public TKey Best => _keys.Min;

public TKey Worst => _keys.Max;

public void Enqueue(TValue node)
{
var key = node.GetKey();

if (!_data.TryGetValue(key, out List<TValue> thisKeyValues))
{
thisKeyValues = new List<TValue>(4);
_data[key] = thisKeyValues;
}

}

public bool IsEmpty => _keys.Count == 0;

public TValue Dequeue()
{
if (IsEmpty)
{
throw new InvalidOperationException();
}

var key = _keys.Min;

List<TValue> thisKeyValues = _data[key];

TValue ret = thisKeyValues[thisKeyValues.Count - 1];
thisKeyValues.RemoveAt(thisKeyValues.Count - 1);
if (thisKeyValues.Count == 0)
{
_data.Remove(key);
_keys.Remove(key);
}

return ret;
}
}

public static class Program
{
public static void Main(string[] args)
{
#if !ONLINE_JUDGE
string input = @"2
5 2 3
1 2 3 1 2
4 3 3
1 1 2 3";
string expectedOutput = @"YES
1 1 1 2 2
YES
1 2 2 3";
#endif

var f = new Factory();
#if !ONLINE_JUDGE
f.InputContent = input;
#endif

var w = f.GetWriter();
Algo p = new Algo(r, w);
p.Run();
w.Flush();

#if !ONLINE_JUDGE
string result = f.GetOutputContent();
var resultLines = result.Split(new[] { "\r", "\n" }, StringSplitOptions.RemoveEmptyEntries);
var expectedLines = expectedOutput.Split(new[] { "\r", "\n" }, StringSplitOptions.RemoveEmptyEntries);

for (int i = 0; i < expectedLines.Length; i++)
{
if (!string.Equals(expectedLines[i].Trim(), resultLines[i].Trim()))
{
throw new InvalidOperationException(\$"Line {i + 1}: expected \"{expectedLines[i]}\", was \"{resultLines[i]}\".");
}
}
#endif
}
}

{
static char[] tokens = new char[4];

{
int size = 0;

bool skipWhiteSpaceMode = true;
while (true)
{
if (nextChar == -1)
{
break;
}

char ch = (char)nextChar;
if (char.IsWhiteSpace(ch))
{
if (!skipWhiteSpaceMode)
{
if (ch == '\r' && (Environment.NewLine == "\r\n"))
{
}
break;
}
}
else
{
skipWhiteSpaceMode = false;
if (size == tokens.Length)
{
char[] a2 = new char[tokens.Length * 2];
Array.Copy(tokens, a2, tokens.Length);
tokens = a2;
}
tokens[size++] = ch;
}
}

}

public static char C(this StreamReader sr)
{
while (true)
{
if (nextChar == -1)
{
// End of stream reached
return (char)0;
}

char ch = (char)nextChar;
if (!char.IsWhiteSpace(ch))
{
return ch;
}
}
}

public static int I(this StreamReader sr)
{
var token = new string(NextToken(sr));
return int.Parse(token);
}

public static double D(this StreamReader sr, bool acceptAnyDecimalSeparator = true)
{
var token = NextToken(sr);
if (acceptAnyDecimalSeparator)
{
var tokens = new string(token).Replace(',', '.');
double result = double.Parse(tokens, CultureInfo.InvariantCulture);
return result;
}
else
{
double result = double.Parse(token);
return result;
}
}

public static decimal M(this StreamReader sr, bool acceptAnyDecimalSeparator = true)
{
var token = NextToken(sr);
if (acceptAnyDecimalSeparator)
{
var tokens = new string(token).Replace(',', '.');
decimal result = decimal.Parse(tokens, CultureInfo.InvariantCulture);
return result;
}
else
{
decimal result = decimal.Parse(token);
return result;
}
}

public static int[] II(this StreamReader r, int n)
{
int[] ret = new int[n];
for (int i = 0; i < n; i++)
ret[i] = r.I();

return ret;
}

public static short[] Digits(this StreamReader r, int n)
{
short[] ret = new short[n];
for (int i = 0; i < n; i++)
ret[i] = (short)(r.C() - (int)'0');

return ret;
}

public static bool[] BB(this StreamReader r, int n)
{
bool[] ret = new bool[n];
for (int i = 0; i < n; i++)
ret[i] = r.C() == '1';

return ret;
}

public static bool[] PlusesMinuses(this StreamReader r, int length)
{
bool[] ret = new bool[length];
for (int i = 0; i < length; i++)
ret[i] = r.C() == '+';

return ret;
}

public static Int16[] SS(this StreamReader r, int n)
{
Int16[] ret = new Int16[n];
for (int i = 0; i < n; i++)
ret[i] = Int16.Parse(r.NextToken());

return ret;
}

public static long[] LL(this StreamReader r, int n)
{
long[] ret = new long[n];
for (long i = 0; i < n; i++)
ret[i] = long.Parse(r.NextToken());

return ret;
}

public static void WriteLine(this StreamWriter w, int i)
{
w.WriteLine(i.ToString());
}

public static void WriteLine(this StreamWriter w, char[] z)
{
w.WriteLine(new string(z));
}

public static void WriteYESNOLine(this StreamWriter w, bool b)
{
w.WriteLine(b ? "YES" : "NO");
}

public static void WriteNums(this StreamWriter w, IEnumerable<int> nn)
{
bool first = true;
foreach (int n in nn)
{
if (first)
{
first = false;
}
else
{
w.Write(' ');
}
w.Write(n);
}
w.WriteLine();
}

public static void WriteNums(this StreamWriter w, IEnumerable<long> nn)
{
bool first = true;
foreach (long n in nn)
{
if (first)
{
first = false;
}
else
{
w.Write(' ');
}
w.Write(n);
}
w.WriteLine();
}
}

public class Factory
{
private StreamWriter _sw;
#if !ONLINE_JUDGE
public string InputContent { get; set; }
private MemoryStream _ms;

public string GetOutputContent()
{
return Encoding.ASCII.GetString(_ms.ToArray());
}
#endif

public StreamWriter GetWriter()
{
return _sw = _sw ?? new StreamWriter(GetOutputStream());
}

Stream GetOutputStream()
{
#if ONLINE_JUDGE
return Console.OpenStandardOutput();
#else
return _ms = new MemoryStream();
#endif
}

{
return _sr = _sr ?? new StreamReader(GetInputStream());
}

Stream GetInputStream()
{
#if ONLINE_JUDGE
return Console.OpenStandardInput();
#else

return new MemoryStream(Encoding.ASCII.GetBytes(InputContent), false);
#endif
}

public void Dispose()
{
_sw?.Dispose();
_sr?.Dispose();
}
}
}


Phoenix and Towers solution codeforces Phoenix and Towers solution codeforces Phoenix and Towers solution codeforces
Phoenix and Towers solution codeforces Phoenix and Towers solution codeforces Phoenix and Towers solution codeforces
Phoenix and Towers solution codeforces Phoenix and Towers solution codeforces Phoenix and Towers solution codeforces

Phoenix and Towers solution codeforces Phoenix and Towers solution codeforces Phoenix and Towers solution codeforces